한 문장에서 반복되는 문자열 중 가장 짧은 문자열 찾기

BOJ 26266] 비즈네르 암호 해독 문제 중

 

S E O U L S E O U L S E O U L...

이런 문자열에서 반복되는 문자열 중 가장 짧은 문자열은 SEOUL이다.

다음을 찾기 위해 KMP 알고리즘을 차용

 

https://blog.naver.com/ndb796/221240660061

30. KMP(Knuth-Morris-Pratt) 알고리즘

 

for (i = 1; i < size; i++) {
		if (v[j] == v[i]) {
			start = i;
			while (i < size && v[j] != v[i]) {
				j++;
				i++;
			}
			if (start == j) {
				break;
			}
			else {
				j = 0;
			}
		}
	}