BOJ 6206 - Milk Patterns

BOJ 6206 - Milk Patterns

라빈카프(문자열 해싱) + 이분탐색으로 푸는게 가장 떠올리기 쉬운 풀이이고 $N \le 20,000$ 이기 때문에 이중이든 삼중이든 안전하게 해시를 하면 무조건 통과할 수 있다.

다른 풀이로는 LCP인데, LCP 배열의 길이가 $K-1$ 인 구간들을 생각해보면 그 구간에서 LCP 배열의 최솟값은 그 다음 이어지는 길이를 의미하므로 이러한 최솟값들 중 최댓값이 정답이다.

문제의 예시를 보자.

1 2 3 2 3 2 3 1 를 Suffix Array, LCP로 나타내면

SA	String	LCP
7	1	1
0	12323231	0
5	231	2
3	23231	4
1	2323231	0
6	31	1
4	3231	3
2	323231	-1

이고 $K-1=1$ 이여서 23231 이 $4$로 가장 크기 때문에 이것이 정답이다.

다음은 해시 풀이 코드이다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }

void solve() {
   int n, k;
   cin >> n >> k;
   vi a(n);
   fv(a);

   vi plist = {31, 97, 17};
   int P = 3;
   vvi pw(P, vi(n + 1, 1));
   for (int p = 0; p < P; p++) for (int i = 1; i <= n; i++) pw[p][i] = md(pw[p][i - 1] * plist[p]);

   // k 번 이상 반복되는 패턴의 길이
   int l = 1, r = n - k + 1, ret = -1;
   while (l <= r) {
      int m = l + (r - l) / 2;
      vi H(P);
      auto getH = [&]() { return H[0] ^ H[1] ^ H[2]; };
      vi hs;
      for (int i = 0; i < m; i++) {
         for (int p = 0; p < P; p++) {
            H[p] = md(H[p] + a[i] * pw[p][m - 1 - i]);
         }
      }
      hs.pb(getH());
      for (int i = m; i < n; i++) {
         for (int p = 0; p < P; p++) {
            H[p] = md(md(H[p] - a[i - m] * pw[p][m - 1]) * plist[p] + a[i]);
         }
         hs.pb(getH());
      }
      sort(all(hs));
      int mx = 0;
      for (int i = 0; i < sz(hs);) {
         int j = i;
         while (j < sz(hs) && hs[i] == hs[j])j++;
         maxa(mx, j - i);
         i = j;
      }
      if (mx >= k) ret = m, l = m + 1;
      else r = m - 1;
   }
   cout << ret;
}