字符串 Alex_Wei

BrotherCall · 2025-04-08 00:52:11 · 个人记录

Manacher

模板：

#include <bits/stdc++.h>
using namespace std;
const int N = 2.2e7 + 5;
int n, m, ans, R[N];
char s[N], t[N];
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  t[0] = '!', t[m = 1] = '@';
  for(int i = 1; i <= n; i++) t[++m] = s[i], t[++m] = '@';
  t[++m] = '#';
  for(int i = 1, c = 0, r = 0; i < m; i++) {
    R[i] = r < i ? 0 : min(R[c * 2 - i], r - i + 1);
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    ans = max(ans, R[i] - 1);
    if(i + R[i] - 1 > r) c = i, r = i + R[i] - 1;
  }
  cout << ans << endl;
  return 0;
}

改编自 Alex_Wei，主要是把回文半径的初始值从 1 改为 0 了。因为在某些规则下，单个字符并非回文串。

题目都做了一遍，评价为目前没有难点。

扩展 KMP

scanf("%s" , c1 + 1);
scanf("%s" , c2 + 1);
int len1 = strlen(c1 + 1) , len2 = strlen(c2 + 1);
z[1] = len2;
for(int i = 2 , l = 0 , r = 0;i <= len2;i ++) {
    z[i] = i > r ? 0 : min(z[i - l + 1] , r - i + 1);
    while(c2[1 + z[i]] == c2[i + z[i]]) z[i] ++;
    if(i + z[i] - 1 > r) {
        l = i , r = i + z[i]- 1;
    }
}

for(int i = 1 , l = 0 , r = 0;i <= len1;i ++) {
    p[i] = i > r ? 0 : min(z[i - l + 1] , r - i + 1);
    while(p[i] < len2 && c2[1 + p[i]] == c1[i + p[i]]) p[i] ++;
    if(i + p[i] - 1 > r) {
        l = i , r = i + p[i] - 1;
    } 
}

扩展 KMP 简述：和 Manacher 原理很像，不断扩充右端点，用已知信息扩充得到该点信息。

用途：得到文本串以 i 为开头的与模式串的 \text{lcp}。

CF526D

相当漂亮的题。

首先题目非常抽象，\texttt{ABAB...A} 这种东西相当抽象，我们肯定是希望相邻的是相同的串。所以我们令 \texttt{C=AB}，题目就转化为了 \texttt{CCC...A}，此时 \texttt{A} 是 \texttt{C} 的一个前缀。

首先说一下直观的 Alex_Wei 的做法，就是既然是一个 k 个相同串组成的前缀，那这个前缀长度肯定是 k 的倍数，枚举 k 的倍数 i，看最小循环节 i - nxt_i 是否是 i / k 的因子。若不是，那这个位置 i 到 (i / k + 1) \times k - 1 肯定不满足题意。

若是，还要看后面多少是 \texttt{C} 的前缀，这个用扩 \text{K} 随便做下就有了。

另外一个不用扩 \text{K} 的做法，首先 i - nxt_i 是循环节，然后 i / (i-nxt_i) 就是循环个数，令他为 cir_i。

我们需要把 cir_i 分给 k，这样每 cir_i / k 个就要并起来，最后剩 cir_i \bmod k 个。

如果 i \bmod (i - nxt_i) = 0，说明最后没有多的部分，那 cir_i \bmod k \le cir_i / k 即可。

否则说明最后多了点循环节的前缀，那需要满足 cir_i \bmod k < cir_i / k 即可。