[백준] 4354번 문자열 제곱

4354 문자열 제곱

문제

---

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

a^0 = "" (빈 문자열)

a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

---

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

출력

---

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

---

풀이)

s = a^n, 가장 큰 n을 찾는게 목표이므로 반복되는 문자열의 최대길이가 아닌 최소길이를 찾아야한다.

반복되는 최소 문자열 길이를 찾아 전체 문자열 길이를 그 길이로 나눈 답을 출력하면 된다.

반복되는 문자열의 길이를 알아내기 위해서 KMP의 실패 함수를 이용했다.

주의할 점

처음에는 실패함수를 돌리고 난 후, 실패 함수 값이 0인 개수를 세어 그것을 전체 길이에 나눠서 답을 도출했다. 

abcd, aaaa, ababab 같은 예시에는 정답이 나오나 반례가 존재했다.

반례) abaaba  

실패 함수값 F[i] : 0 0 1 1 2 3

실제 정답: 6/3 =2     

0인 개수 세었을 때 오류 정답: 6/2 =3

실패 함수 값 중 0인 개수를 이용하는 것이 아닌 실패 함수의 마지막 값을 이용해야 한다.

전체 길이 - 실패 함수의 마지막 값 = 반복되는 문자열의 최소 길이 이다.

코드)

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
 
int F[1000003];
int main() {
    string s;
    while (true)
    {
        cin >> s;
        if (s == ".") break;
        for (int i = 0; i < s.length(); i++) {
            F[i] = 0;
        }
        int i = 1;
        int j = 0;
        while (i<s.length())
        {
            if (s[i] == s[j]) {
                F[i] = j + 1;
                i += 1;
                j += 1;
            }
            else if (j > 0) {
                j = F[j - 1];
            }
            else {
                F[i] = 0;
                i += 1;
            }
        }
 
        int last = F[s.length() - 1];//마지막 값
        if (last == 0) {
            printf("1\n");
        }
        else {
            printf("%d\n", s.length() / (s.length() - last));
        }
        
    }
    return 0;
}