'한국디지털미디어고등학교'는 너무 길다. timer 1s memory 1024MB

디미고의 공식 명칭인 '한국디지털미디어고등학교'는 너무 길다. 그래서 한국디지털미디어고등학교를 문과 계열의 디지털콘텐츠과와 이비지니스과 학교, 이과 계열의 웹프로그래밍과와 해킹방어과 학교 즉, 문과 학교와 이과 학교 둘로 나누어 학교 이름을 줄이려 한다. 학생회는 나눈 두 학교의 이름을 새로 지어야 한다.

학생회는 한국디지털미디어고등학교의 정체성을 지키기 위해 두 학교의 이름을 원래 학교 이름의 연속된 앞부분과 나머지 뒷부분으로 나누어 정하기로 했다. 예를 들어 "KoreaDigitalMediaHighSchool"을 앞부분 "KoreaDigital"과 뒷부분 "MediaHighSchool"으로 나눌 수 있다. 또한 대소문자를 구분하며 앞부분 또는 뒷부분이 빈 문자열이어도 된다.

이때 문과 계열과 이과 계열은 서로 라이벌 의식을 가지고 있기 때문에 나누어진 두 학교의 이름이 최대한 달랐으면 했다. 학생회는 이를 객관적으로 판단하기 위해 불일치도라는 값을 사용하기로 했다. 불일치도는 학교 이름을 나눈 두 문자열을 각각 A, B라고 했을 때 \mathrm{min}(|A|, |B|) - \mathrm{LCS}(A, B)이다. |A|는 A의 길이이다.

\mathrm{LCS}(A, B)는 A, B 모두의 부분 문자열이 되는 문자열 중 가장 긴 문자열의 길이이다. 예를 들면, "ABCD"와 "ABDF"의 공통 부분 문자열 중 가장 긴 문자열은 "ABD"로 \mathrm{LCS}("ABCD", "ABDF")는 3이다. 부분 문자열은 원래 문자열에서 0개 이상의 문자를 제거해 만든 문자열이다.

한국디지털미디어고등학교를 잘 나눌 수 있도록 가능한 불일치도의 최댓값을 구하자.