백준 1498 - 주기문

https://www.acmicpc.net/problem/4354

사전 지식

이 문제를 KMP로 풀고 와야 한다.

 

https://www.acmicpc.net/problem/4354

4354번: 문자열 제곱

풀이

문자열 제곱을 제대로 이해하고 왔다면 KMP 실패 함수에 다음 성질이 있음을 알 것이다.

 

길이 x의 문자열이 주기성을 만족하려면 n - x개의 접미사와 n - x개의 접두사가 같아야 한다. 또한 x|n을 만족해야 한다.(|은 정수론에서 배수관계를 나타내는 기호)

 

일단 실패 테이블을 구하자.

 

그러면 테이블에 n - x개의 서로 같은 문자열의 길이를 구할 수 있다. 문제에서는 substring에 대해 주기를 구할 수 있냐고 묻고 있으므로 각 인덱스마다 (i + 1) - pi[i] (0-indexed)의 값으로 x를 구하고 나눠 떨어지는 것마다 출력하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
string s;
 
vector<int> bake_pi(string &pat)
{
  vector<int> ret(pat.size());
  int j = 0;
  for (int i = 1; i < pat.size(); i++)
  {
    while (j and pat[j] != pat[i]) j = ret[j - 1];
    ret[i] = pat[j] == pat[i] ? ++j : 0;
  }
  return ret;
}
 
void solve()
{
  cin >> s;
 
  auto pi = bake_pi(s);
  for (int i = 1; i < pi.size(); i++)
  {
    int candidate = (i + 1) - pi[i];
    if ((i + 1) % candidate == 0 and (i + 1) != candidate)
    {
      cout << i + 1 << ' ' << (i + 1) / candidate << '\n';
    }
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록