[백준 4354] 문자열 제곱 (C#, C++) - soo:bak

문제 링크

4354번 - 문자열 제곱

설명

문자열 s가 어떤 문자열 a를 n번 이어붙인 형태일 때, 가능한 최대 n을 구하는 문제입니다.

입력은 여러 테스트케이스로 주어지며, 마침표가 나오면 종료합니다.

접근법

먼저, 문자열이 어떤 패턴을 반복하는 형태라면 접두사와 접미사가 겹치는 특성이 있습니다. 예를 들어 abcabcabc는 abc를 3번 반복한 형태인데, 앞의 abcabc와 뒤의 abcabc가 겹칩니다.

다음으로, 부분 일치 테이블을 계산합니다. 테이블의 마지막 값은 전체 문자열에서 접두사와 접미사가 일치하는 최대 길이입니다. abcabcabc의 경우 마지막 값은 6입니다.

이후, 전체 길이에서 이 값을 빼면 최소 주기 길이가 됩니다. 9 - 6 = 3이므로 주기는 abc입니다. 전체 길이가 주기 길이로 나누어떨어지면 9 / 3 = 3이 반복 횟수가 됩니다.

만약 나누어떨어지지 않으면 완전한 반복이 아니므로 답은 1입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int[] BuildPi(string s) {
      var n = s.Length;
      var pi = new int[n];
      for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) pi[i] = ++j;
      }
      return pi;
    }

    static void Main(string[] args) {
      while (true) {
        var s = Console.ReadLine()!;
        if (s == ".") break;
        var pi = BuildPi(s);
        var L = s.Length;
        var k = pi[L - 1];
        var period = L - k;
        var ans = (L % period == 0) ? L / period : 1;
        Console.WriteLine(ans);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  while (cin >> s) {
    if (s == ".") break;
    int L = s.size();
    vi pi(L, 0);
    for (int i = 1, j = 0; i < L; i++) {
      while (j > 0 && s[i] != s[j]) j = pi[j - 1];
      if (s[i] == s[j]) pi[i] = ++j;
    }
    int k = pi[L - 1];
    int period = L - k;
    int ans = (L % period == 0) ? L / period : 1;
    cout << ans << "\n";
  }

  return 0;
}