[BOJ 1305]

문제 바로가기 : https://www.acmicpc.net/problem/1305
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

BOJ 4354에서 썼던 코드를 슥슥 지우고 P_len을 출력해주면 답이다.
그래도 다시 풀어보는 느낌으로 포인트가 되는 부분을 몇가지 적자면,
KMP 알고리즘에 쓰였던 failure function의 의미를 아는게 중요했다. 예를 들어보자.

T :       a a b a a a
saveT[] : 0 1 0 1 2 2

여기서 saveT[]가 의미하는건 뭘까? 나는 saveT[]번째까지 반복됐어라고 말해준다고 생각하면 될 것 같다.
주어진 총 문자열에서 어디까지 반복됐는지를 알아내는(정확히는 반복되는 최소한의 길이) 것이기 때문에 마지막에 주목하자.
saveT[5]는 2번째까지 반복이 됐다. 반복이 됐다는건 생략해도 된다는 말이다. 중복이 됐으니까!
그럼 주어진 총 문자열 길이에서 saveT[마지막]을 빼주면 답이 되겠다.