[C++] 알고스팟/문자열 검색 - 작명하기

문제 링크

https://algospot.com/judge/problem/read/NAMING

algospot.com :: NAMING

 

접두사와 접미사가 같은 문자열을 찾기 위해 KMP알고리즘의 부분 일치 테이블(혹은 failure function으로 불림)을 사용해야 합니다.

 

부분 일치 테이블은 문자열의 첫 번째와 두 번째 부분문자열부터 오른쪽으로 하나씩 늘려가며 접두사도 되고 접미사도 되는 문자열의 길이를 배열의 해당 인덱스에 넣어줍니다.

 

부분 일치 테이블을 구하고 나면 s의 접미사와 접두사가 같은 문자열이 a, ab가 있는 것을 확인할 수 있습니다.

문제에서는 전체 문자열 s의 접두사와 접미사가 되는 문자열이니 a는 해당이 되지 않고 ab가 정답이 됩니다.

또한 전체 문자열인 abcab도 접두사와 접미사가 될 수 있으므로 abcab 또한 정답이 됩니다.

 

 

예제 입력을 살펴보면 위의 경우보다 더 많은 문자열이 정답이 됩니다.

먼저 전체 문자열은 접두사와 접미사가 같기 때문에 가장 먼저 문자열의 길이를 정답으로 넣어줍니다.

그리고 다음의 위치로 pi[k-1]를 가르킵니다.

 

위에서 가르킨 pi의 값이 그 다음의 문자열 길이가 됩니다.

문자열 길이 9만큼 접두사와 접미사가 같은 다음 문자열이 나오기 때문입니다.

이렇게 k의 값을 정답으로 먼저 넣고 다음 k를 pi[k-1]로 가르키면서 k가 0이 될 때까지 반복해주면 답을 구할 수 있습니다.

 

구현 코드