kmp. [1701]

[1. 문제 설명]

https://www.acmicpc.net/problem/1701

---

[2. 풀이 접근]

얼핏보면 kmp 와는 관련이 없어 보이지만, 

kmp 에서 부분 일치 테이블을 이용하여 풀 수 있다.

 

부분 일치 테이블에 저장된 값이 의미하는 바를 생각하면

• n 개의 글자만큼 일치 했을 때,
• 접두사도 되고 접미사도 되는 최대 길이 이다.

이 값이 0보다 크다면 동일한 부분문자열이 전체 문자열에서 앞에도 오고 뒤에도 오게 된다.

즉, 부분 문자열이 적어도 두번 발생하게 된다.

 

그래서, 입력으로 주어지는 문자열에 대해서 부분 일치 테이블 계산 한 뒤,

여기서 최대값을 출력하면 될 것 같지만,

 

좀 더 고민해야 하는 부분이 있다.

아래 입력에 대해서는 정확한 결과를 구하지 못한다.

• qbqtzqqt

위 문자열에 대해서 부분 일치 테이블을 구하여 최대 값을 구한다면 0이 된다.

즉, 모든 부분 문자열에 대해서 고려하지 않는 것이다.

 

그래서 아래와 같이 앞에서 부터 한글자씩 제외하면서 부분 일치 테이블을 구하면서, 

모든 부분 문자열에 대해서 최대 값을 갱신해야 한다.

• qbqtzqqt
• bqtzqqt
• qtzqqt
• tzqqt
• zqqt
• qqt
• qt
• q

---

[3. 코드]