马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
包括 :
哈希, manacher, 字典树, KMP
一些思考:
字符串题首先想哈希
kmp 的求 next 数组过程其实是在 fail 树上的遍历
要善用 next 数组的前后缀相等性质
判断长字符串想倍增比较
利用前缀后缀相同来构造不等式, 找上界下界
s 的最小循环节是 s.len - next[s.len]
线段树维护哈希
马拉车板子cin >> n >> s;
t = "$#";
for (int i = 0; i < n; i++) {
t.push_back(s[i]);
t.push_back('#');
}
t.push_back('&');
n = t.size() - 1;
// p[c] 以 c 为中心能扩展的最大步数
// R 最靠右的回文串覆盖区域, C 是 R 的中心
p[1] = 1;
int R = 1, C = 1;
for (int i = 2; i <= n; i++) {
// 如果在覆盖范围内, 先取一个 p 的最小值
if (i <= R)
p[i] = min(p[C * 2 - i], R - i + 1);
// 向外扩展看看是否可以继续
while (t[i + p[i]] == t[i - p[i]]) p[i]++;
// 如果比 R 大就更新
if (i + p[i] - 1 >= R)
C = i, R = i + p[i] - 1;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, p[i] - 1);
}
cout << ans;
字符串周期
利用 next 数组的含义 (最长相等前后缀)可以知道如果有重叠就会是周期, 判断能否整除即可while (1) {
cas++;
cin >> n;
if (!n)
break;
cin >> (s + 1);
cout << "Test case #" << cas << '\n';
for (int i = 2; i <= n; i++) {
j = nxt[i - 1];
while (j && s[j + 1] != s[i]) j = nxt[j];
if (s[j + 1] == s[i])
j++;
nxt[i] = j;
if (j * 2 >= i && !(i % (i - j))) {
cout << i << ' ' << (i / (i - j)) << '\n';
}
}
}
字符串大师
通过最小循环节的结论, 求出原来的 nxt 数组
接下来构造, 如果 nxt 大于 0 就跳到前面去, 字符就是那个
图个 nxt 是 0 就往前跳, 把出现的字符都记下来, 当前的填字符是没有出现的字符cin >> n >> nxt[1];
s[1] = 'a';
nxt[1]--;
cout << s[1];
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
nxt[i] = i - x;
if (!nxt[i]) {
// 注意这里要设为 1, 因为位置 1 的 a 不会被算进去 (nxt[1] == 0)
// 为什么 i 的 nxt 值是 0 呢? 是因为不管多长的前缀都不和后缀相等
// 类比 kmp 求法, 每次向前跳, 只要不和 nxt[j] 相等就可以继续等于 0
st = 1;
for (int j = nxt[i - 1]; j; j = nxt[j]) {
st |= (1 << (s[j + 1] - 'a'));
}
for (int j = 0; j < 26; j++) {
if ((st >> j) & 1)
continue;
s[i] = 'a' + j;
break;
}
} else {
s[i] = s[nxt[i]];
}
cout << s[i];
}
动物园ans = 1;
for (int i = 2, j = 0; i < s.size(); i++) {
// nxt[i] 相当于 i 的父节点, 求 nxt 数组相当于对这个树 dfs
// 由于父节点肯定小于 i, 我们可以在维护栈中的指针 j 指向最大的 x, x*2 <= i
// 指针移动是 O(n) 的
while (j && s[i] != s[j + 1]) j = nxt[j];
if (s[j + 1] == s[i])
j++;
while (j * 2 > i) j = nxt[j];
ans = (ans * (cnt[j] + 1)) % P;
}
P4696 [CEOI2011] Matching
线段树维护 hash, 支持插入删除, 注意每次加的是增量
P4036 [JSOI2008] 火星人
离线, 搞出每个字符最终的位置, 然后线段树维护 hash, 每次删除节点就把 siz 调为 1 即可
不知怎么的就是调不出来, 80... |