[BOJ] 1498 주기문

문제 링크

www.acmicpc.net/problem/1498

풀이

KMP 문제이다.

문자열의 길이가 $a$이고 마지막 인덱스에 해당하는 실패함수의 값이 $b$라고 하자. 이때, $a-b$ 값이 $a$의 약수라면 길이 $a$짜리 문자열은 길이 $a-b$짜리 prefix의 반복임을 알 수 있다. 문제에서 $n$의 값이 1보다 커야 주기문으로 인정하므로, 실패함수의 값이 0보다 커야 한다.

전체 시간복잡도는 $O(|S|)$이다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int main() {
    fastio;
    char S[1000001];
    cin >> S;

    int fail[1000000]; fail[0] = 0;
    for (int i = 1, j = 0; S[i]; ++i) {
        while (j && S[i] != S[j]) j = fail[j - 1];
        if (S[i] == S[j]) fail[i] = ++j;
    }

    for (int i = 0; S[i]; ++i) {
        int len = i + 1 - fail[i];
        if (fail[i] && (i + 1) % len == 0) cout << i + 1 << ' ' << (i + 1) / len << endl;
    }

    return 0;
}

Java 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();

        int[] fail = new int[S.length()];
        for (int i = 1, j = 0; i < S.length(); ++i) {
            while (j > 0 && S.charAt(i) != S.charAt(j)) j = fail[j - 1];
            if (S.charAt(i) == S.charAt(j)) fail[i] = ++j;
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < S.length(); ++i) {
            int len = i + 1 - fail[i];
            if (fail[i] != 0 && (i + 1) % len == 0) {
                ans.append(i + 1 + " " + (i + 1) / len + "\n");
            }
        }

        System.out.println(ans.toString());
    }
}