字符串

userId_undefined
Asdfre
时空双修者

2026-08-03 18:42:27

发布于：广东

67阅读
0回复
0点赞

Hash

一个能将O(n)O(n)比较转化为O(1)O(1)的高效方法，本质上是将字符串转化为pp进制数（通常为1333113331等）为避免冲突一般这样设定，当然本文章不讨论有关冲突问题，还是说一个吧（ber。而且我一般在代码中用单模数HashHash时一般用unsignedunsigned longlong longlong自然溢出，双模数HashHash视情况。

H(s)=∑i=1lensiplen−iH(s) = \sum_{i=1}^{len} {s_i p^{len-i}}

并且我们得知一个前缀HH值，我们可以求出区间HH值：

H(L,R)=H(R)−H(L−1)×pr−l+1H(L,R) = H(R) - H(L-1) \times p^{r-l+1}

如何卡掉一个自然溢出的HashHash？

这就是有名的Thue−MorseThue-Morse序列卡自然溢出：

定义S0=aS_0=a，T0=bT_0=b，令Si=Si−1+Ti−1S_i=S_{i-1}+T_{i-1}，Ti=Ti−1+Si−1T_i=T_{i-1}+S_{i-1}即可。

为什么能卡掉？我们考虑从差值下手

i=1i=1：Hash(S1)−Hash(T1)=(a−b)(base−1)Hash(S_1)-Hash(T_1)=(a-b)(base-1)
i=2i=2：Hash(S2)−Hash(T2)=(a−b)(base−1)(base2−1)Hash(S_2)-Hash(T_2)=(a-b)(base-1)(base^2-1)
.......

因为常见的basebase都用质数，除了22都是奇数，所以(base-1)为偶数，以此类推后面都为偶数，即都包含至少一个22的因子。当nn仅仅为15个左右，22的因子至少都有6464个，溢出后为00，被定义为相等，这样就卡掉了自然溢出。

Hash Killer I

如何让长度为ll的子串匹配错误，我们可以认为定义l=8192=213l=8192=2^{13}，代码中滑动窗口取出+排序去重，一定会错误，这样就处理好了。

那怎么生成长10510^5长度的Thue−MorseThue-Morse序列呢？

这里直接给结论：aa和bb分布完全取决于当前这个位置二进制数中11个数的奇偶性，若为奇则为aa，bb反之。

当然你直接拼接一样能过。。。

#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init(){
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	void Main()
	{
		cout<<100000<<' '<<8192<<endl;
		string s="a",t="b";
		for (int i=1;i<18;++i){
			string curs=s;
			s=s+t;
			t=t+curs;
		}
		cout<<string(s.begin(),s.begin()+100000);
	}
}
int main()
{
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

那如果模数为109+710^9+7怎么办，分两种情况：

1.basebase固定，根据生日悖论，MM个状态找到一对相同的，大约需要M\sqrt{M}个数据即可，本地跑到错误数据Hack即可；

2.basebase纯随机，方法更简单，随机长度10510^5的aa，bb随机出现的串即可。为什么对：我们人为设定Len=2×104Len=2 \times 10^4，那么总共有K=8×104K=8 \times 10^4个，两两对比有(8×104)22≈3.2×109\frac {(8 \times 10^4)^2}{2} \approx 3.2 \times 10^9，模数为109+710^9+7，期望次数大约为3.23.2次，根据泊松分布，P=1−e−3.2≈95.9P=1-e^{-3.2} \approx 95.9%。

Hash Killer II

当然我第一发WA了一个点（碰到了4.14.1%的失败概率，我是不是可以买彩票了？？！），多交几次，毕竟是随机数嘛。

#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init(){
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	void Main()
	{
		int n=1e5,l=2e4;
		mt19937_64 myrnd(time(nullptr));
		string ans="";
		for (int i=1;i<=n;++i){
			ll c=myrnd()+133331,cc=myrnd()+233333;
			if ((c+cc)%2ll==0) ans+='a';
			else ans+='b';
		}
		cout<<n<<' '<<l<<endl<<ans;
	}
}
int main()
{
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

知道完这些，我们就可以配合二分等解决一些问题了：

通配符匹配

@cjdst 别吵，我在思考！！！！（绷

注意到通配符的个数不超过1010，我们可以在原串上拆分成 ≤21\le 21串为∗*，??，和纯字符串，记为TokenToken。

再考虑一个dpi,jdp_{i,j}表示主串前ii个TokenToken能不能和模式串前jj个字符。

接着就可以思考转移了：

1.第ii个TokenToken为??，强制匹配第jj个字符：dpi,j=dpi−1,j−1dp_{i,j}=dp_{i-1,j-1}。
2.第ii个TokenToken为∗*，可以匹配或者继承j−1j-1的状态以继续匹配更多字符：dpi,j=dpi−1,jdp_{i,j}=dp_{i-1,j} OROR dpi,j−1dp_{i,j-1}。
3.第ii个TokenToken为纯字符串，直接HashHash判断就行：
dpi,j=dpi−1,j−lendp_{i,j}=dp_{i-1,j-len} ANDAND Hash(S,j−len+1,j)==H(i)Hash(S,j-len+1,j)==H(i)

最后答案是dpcntToken,mdp_{cntToken,m}即可。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr ull P = 13331, N = 1e5+3;
	struct Token {
		int op;
		ull hash_val;
		int len;
		Token (int _o = 0, ull _h = 0, int _l = 0) : op(_o), hash_val(_h), len(_l) { }
	};
	void Main() {
		string s;
		cin >> s;
		vec<ull> h(N, 0), p(N, 1);
		for (int i = 1; i < N; ++i) p[i] = p[i - 1] * P;
		vec<Token> a;
		a.pb({-1, 0, 0});
		string t = "";
		for (char c : s) {
			if (c == '?' || c == '*') {
				if (!t.empty()) {
					ull cur = 0;
					int l = 0;
					for (char cc : t) cur = cur * P + cc, ++l;
					a.pb({2, cur, l});
					t = "";
				}
				a.pb({c == '?' ? 0 : 1, 0, c == '?' ? 1 : 0});
			} else t += c;
		}
		if (!t.empty()) {
			ull cur = 0;
			int l = 0;
			for (char c : t) cur = cur * P + c, ++l;
			a.pb({2, cur, l});
		}
//		for (auto [op,val,len]:a) cout<<op<<' '<<val<<' '<<len<<endl;
		int q;
		cin >> q;
		auto get_hash = [&](int l, int r)->ull{
			return h[r] - h[l - 1] * p[r - l + 1];
		};
		int n = a.size() - 1;
		while (q--) {
			string ss;
			cin >> ss;
			int m = ss.size();
			ss = '#' + ss;
			vec<vec<char>> dp(23, vec<char>(m + 1, 0));
			for (int i = 1; i <= m; ++i) h[i] = h[i - 1] * P + ss[i];
			dp[0][0] = 1;
			for (int i = 1; i <= n; ++i) {
				if (a[i].op == 0) {
					for (int j = 1; j <= m; ++j) dp[i][j] = dp[i - 1][j - 1];
				} else if (a[i].op == 1) {
					dp[i][0] = dp[i - 1][0];
					for (int j = 1; j <= m; ++j) dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
				} else {
					for (int j = a[i].len; j <= m; ++j) dp[i][j] = dp[i - 1][j - a[i].len] && (get_hash(j - a[i].len + 1, j) == a[i].hash_val);
				}
			}
			cout << (dp[n][m] ? "YES" : "NO") << endl;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

DNA

比较经典的二分+Hash题目，枚举起点ii，二分长度，遇到匹配不上就跳过继续二分，最多匹配不上3次，若合法匹配整个模式串答案+1+1。

时间复杂度O(Tnlog⁡n)O(T n \log n)，显然跑不满，稳过。

代码好写捏：

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr ull N = 1e5+5, P = 133331;
	ull h1[N], h2[N], p[N];
	ull get1(int l, int r) {
		return h1[r] - h1[l - 1] * p[r - l + 1];
	}
	ull get2(int l, int r) {
		return h2[r] - h2[l - 1] * p[r - l + 1];
	}
	void Main() {
		string s, t;
		cin >> s >> t;
		int n = s.size(), m = t.size();
		if (n < m) {
			cout << 0 << endl;
			return ;
		}
		s = '$' + s, t = '#' + t;
		p[0] = 1;
		for (int i = 1; i < N; ++i) p[i] = p[i - 1] * P;
		for (int i = 1; i <= n; ++i) h1[i] = h1[i - 1] * P + s[i];
		for (int i = 1; i <= m; ++i) h2[i] = h2[i - 1] * P + t[i];
		int res = 0;
		for (int i = 1; i <= n - m + 1; ++i) {
			int cnt = 0, p1 = i, p2 = 1;
//			cout<<"i:"<<i<<endl;
			while (cnt <= 3) {
				int l = 0, r = m - p2 + 1, aans = 0;
				while (l <= r) {
					int mid = (l + r) >> 1;
					if (get1(p1, p1 + mid - 1) == get2(p2, p2 + mid - 1)) {
						aans = mid;
						l = mid + 1;
					} else r = mid - 1;
				}
//				cout<<"aans:"<<aans<<endl;
				p1 += aans, p2 += aans;
				if (p2 > m) {
					++res;
					break;
				}
				++cnt, ++p1, ++p2;
//				cout<<cnt<<' '<<p1<<' '<<p2<<endl;
			}
//			cout<<endl<<endl;
		}
		cout << res << endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

CF580E Kefa and Watch

一道线段树维护Hash的肥肠有意思的题目。

先考虑最先的问题，如何判断一个字符串是否有周期dd？

这直接给结论：判断S[L+d,R]S[L+d,R]是否等于S[L,R−d]S[L,R-d]即可，证明我感觉有点复杂，就不说了（蒻。

考虑带修，区间覆盖+区间查询，考虑用线段树维护Hash。

upup怎么做？观察H(s)H(s)的计算方式，合并左右子树时，得到H(rt)=H(ls)∗prs.len+H(rs)H(rt)=H(ls)*p_{rs.len}+H(rs)。

区间覆盖怎么做？当我们修改[l,r][l,r]时，覆盖值为cc，发现一段区间[x,y][x,y]被其完全覆盖：
H([x,y])=∑i=0len−1c∗Pi=c∗∑i=0len−1PiH([x,y])=\sum_{i=0}^{len-1} {c*P^i}=c*\sum_{i=0}^{len-1} {P^i}，len=y−x+1len=y-x+1

所以我们可以预处理sumpi=∑j=0i−1Pisump_i= \sum_{j=0}^{i-1} {P^i}即可，这样我们就做完了。

但是codeforces卡自然溢出HashHash，（怒！

所以用了双模数过的：

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr ll P1 = 13331, P2 = 23333, mod1 = 1e9+7, mod2 = 1e9+9;
	constexpr int N = 1e5+5;
	ll p1[N], sump1[N], p2[N], sump2[N];
	void init() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		p1[0] = 1, sump1[0] = 0;
		p2[0] = 1, sump2[0] = 0;
		for (int i = 1; i < N; ++i) {
			p1[i] = p1[i - 1] * P1 % mod1, sump1[i] = (sump1[i - 1] + p1[i - 1]) % mod1;
			p2[i] = p2[i - 1] * P2 % mod2, sump2[i] = (sump2[i - 1] + p2[i - 1]) % mod2;
		}
	}
	struct Node {
		ll val1, val2, tag;
		int len;
		Node (ll v1 = 0, ll v2 = 0, ll t = -1, int l = 0) : val1(v1), val2(v2), tag(t), len(l) {}
#define val1(rt) tr[rt].val1
#define val2(rt) tr[rt].val2
#define len(rt) tr[rt].len
#define tag(rt) tr[rt].tag
	} tr[N << 2];
	void up(int rt) {
		val1(rt) = (val1(rt << 1) * p1[len(rt << 1 | 1)] % mod1 + val1(rt << 1 | 1)) % mod1;
		val2(rt) = (val2(rt << 1) * p2[len(rt << 1 | 1)] % mod2 + val2(rt << 1 | 1)) % mod2;
	}
	void build(int rt, int l, int r, const string& s) {
		len(rt) = r - l + 1;
		if (l == r) {
			val1(rt) = s[l];
			val2(rt) = s[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid, s);
		build(rt << 1 | 1, mid + 1, r, s);
		up(rt);
	}
	void change(int rt, ull v) {
		val1(rt) = v * sump1[len(rt)] % mod1;
		val2(rt) = v * sump2[len(rt)] % mod2;
		tag(rt) = v;
	}
	void down(int rt) {
		if (~tag(rt)) {
			change(rt << 1, tag(rt));
			change(rt << 1 | 1, tag(rt));
			tag(rt) = -1;
		}
	}
	void update(int rt, int l, int r, int x, int y, ll c) {
		if (x <= l && r <= y) {
			change(rt, c);
			return ;
		}
		down(rt);
		int mid = (l + r) >> 1;
		if (x <= mid) update(rt << 1, l, mid, x, y, c);
		if (y > mid) update(rt << 1 | 1, mid + 1, r, x, y, c);
		up(rt);
	}
	Node query(int rt, int l, int r, int x, int y) {
		if (x <= l && r <= y) return tr[rt];
		down(rt);
		int mid = (l + r) >> 1;
		Node L, R, res;
		if (y <= mid) return query(rt << 1, l, mid, x, y);
		if (x > mid) return query(rt << 1 | 1, mid + 1, r, x, y);
		L = query(rt << 1, l, mid, x, y), R = query(rt << 1 | 1, mid + 1, r, x, y);
		res.len = L.len + R.len;
		res.val1 = (L.val1 * p1[R.len] % mod1 + R.val1) % mod1;
		res.val2 = (L.val2 * p2[R.len] % mod2 + R.val2) % mod2;
		return res;
	}
	void Main() {
		int n, m, k;
		cin >> n >> m >> k;
		string s;
		cin >> s;
		s = '#' + s;
		build(1, 1, n, s);
		for (int i = 1; i <= m + k; ++i) {
			int op, l, r;
			cin >> op >> l >> r;
			if (op == 1) {
				ll c;
				cin >> c;
				c += '0';
				update(1, 1, n, l, r, c);
			} else {
				int d;
				cin >> d;
				if (l + d > r || r - d < l) {
					if (d == r - l + 1) {
						cout << "YES" << endl;
					} else cout << "NO" << endl;
					continue;
				}
				Node ans1 = query(1, 1, n, l + d, r), ans2 = query(1, 1, n, l, r - d);
				if (ans1.val1 == ans2.val1 && ans1.val2 == ans2.val2) {
					cout << "YES" << endl;
				} else cout << "NO" << endl;
			}
		}
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

KMP

一个高效O(n)O(n)单模式串匹配的工具。

主要思路是用nxtinxt_i记录S[1...i]S[1...i]的最长相等的真前缀和真后缀（真前后缀比其普通前后缀不包含本身），每次在jj失配不用从头开始跳，从nxtjnxt_j开始匹配。

有个重要结论：如果一个字符串长度为NN，则这个字符串最小循环节为N−nxtNN-nxt_N（前提为NN modmod (N−nxtN)=0(N-nxt_N)=0）

贴个模版代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s,t;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    s='$'+s,t='#'+t;
    vector<int> nxt(m+1,0);
    for (int i=2,j=0;i<=m;++i){
        while(j&&t[i]!=t[j+1]) j=nxt[j];
        if (t[i]==t[j+1]) ++j;
        nxt[i]=j;
    }
    vector<int> ans;
    for (int i=1,j=0;i<=n;++i){
        while(j&&s[i]!=t[j+1]) j=nxt[j];
        if (s[i]==t[j+1]) ++j;
        if (j==m){
            ans.push_back(i-m+1);
            j=nxt[j];
        }
    }
    for (int i:ans) cout<<i<<endl;
    for (int i=1;i<=m;++i) cout<<nxt[i]<<' ';
    return 0;
}

接下了开始应用咯~

Censoring S

做完这道会对KMPKMP有一个更深的理解。

核心就是：每次匹配成功，我们把jj移到匹配成功位置的前一个字符所在模式串匹配的nxtnxt最大位置，用一个ftift_i记录即可，前面删除操作用栈维护即可。

#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init(){
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	void Main()
	{
		string s,t;
		cin>>s>>t;
		int n=s.size(),m=t.size();
		s='#'+s,t='$'+t;
		vec<int> nxt(m+1,0);
		for (int i=2,j=0;i<=m;++i){
			while(j&&t[i]!=t[j+1]) j=nxt[j];
			if (t[i]==t[j+1]) ++j;
			nxt[i]=j;
		}
		vec<int> ft(n+1,0),stk(n+1,0);
		int top=0;
		for (int i=1,j=0;i<=n;++i){
			while(j&&s[i]!=t[j+1]) j=nxt[j];
			if (s[i]==t[j+1]) ++j;
			ft[i]=j,stk[++top]=i;
			if (j==m){
				top-=m,j=ft[stk[top]];
			}
		}
		string ans="";
		for (int i=1;i<=top;++i) ans+=s[stk[i]];
		cout<<ans;
	}
}
int main()
{
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

CF2205E

一道非常有思维含量的题目，建议先思考，这个题我在这个帖子讲。

KMP凸包专题中考虑同构的问题

好题好题！！（lyy为什么没有场切？）直接传送即可食用。鬼知道这道题代码调了多久，结果是数组大小写错了（😡

Manacher

O(n)O(n)求最长回文串的工具。

核心思想就是在字符串中间加'#'号使其为偶数，再维护中心点CC和右边界RR,利用前面处理出来的现成值更新现在的值（要受限于当前维护的区间），最后再暴力匹配，能将复杂度降到O(n)O(n)。

pip_i代表新的字符串的最长回文半径，Ans=maxi=1npi−1Ans=max_{i=1}^{n} {p_i-1}（可以想想为什么）。

模版：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
#define endl "\n"
#define vec std::vector
constexpr int N = 2.2e7 + 5;
char s[N];
int n, p[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S;
    cin >> S;
    s[n++] = '^', s[n++] = '#';
    for (char c : S)
    {
        s[n++] = c;
        s[n++] = '#';
    }
    s[n++] = '$';
    int c = 0, r = 0, ma = 0;
    for (int i = 1; i < n - 1; ++i)
    {
        if (i < r)
        {
            int j = 2 * c - i;
            p[i] = min(p[j], r - i);
        }
        else
            p[i] = 1;
        while (s[i + p[i]] == s[i - p[i]])
            ++p[i];
        if (i + p[i] > r)
        {
            c = i;
            r = i + p[i];
        }
        ma = max(ma, p[i] - 1);
    }
    cout << ma;
    return 0;
}

ABB

非常简单的ManacherManacher应用，只是要把边界判清楚。

先跑一遍ManacherManacher，再枚举新串中的每个位置，判断对应到原串中（有可能是空，要判清楚）是否以这个点为中心的回文串延伸到最右端，如果是取最大值即可。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define vec std::vector
using ll=long long;
using ull=unsigned long long;
constexpr int N=8e5+5;
char s[N];
int n,k,p[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string S;
	cin>>n>>S;
	s[k++]='&',s[k++]='#';
	for (char c:S) {
		s[k++]=c;
		s[k++]='#';
	}
	s[k++]='$';
	int c=0,r=0,ma=0;
	for (int i=1;i<k;++i){
		if (i<r){
			int j=2*c-i;
			p[i]=min(p[j],r-i);
		}else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) ++p[i];
		if (i+p[i]>r){
			c=i,r=i+p[i];
		}
	}
	for (int i=k-1;i>=0;--i){
		if (s[i]=='#') {
			int len=(p[i]-1)/2;
			if (n-(i/2+1)+1==len) {
				ma=max(p[i]-1,ma);
			}
		}else {
			int len=p[i]/2-1;
			if (n-(i/2)==len){
				ma=max(p[i]-1,ma);
			} 
		}
	}
	cout<<n-ma;
	return 0;
}

[POI 2010] ANT-Antisymmetry

也比较简单，只用在跑ManacherManacher时更改一下判断条件，用一个chkchk即可解决：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define vec std::vector
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
constexpr int N=1e6+5;
int n,p[N],m;
string S;
char s[N];
ll ans=0;
bool chk(char c1,char c2){
	if (c1==c2&&c1=='#') return true;
	if (c1!=c2&&((c1=='0'&&c2=='1')||(c1=='1'&&c2=='0'))) return true;
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>S;
	s[m++]='^';
	s[m++]='#';
	for (char c:S){
		s[m++]=c;
		s[m++]='#';
	}
	s[m++]='&';
	int c=0,r=0;
	for (int i=1;i<m-1;++i){
		if (i<r){
			int j=2*c-i;
			p[i]=min(p[j],r-i);
		}else p[i]=0;
		while(i-p[i]>0&&chk(s[i-p[i]],s[i+p[i]])) ++p[i];
		if (i+p[i]>r){
			c=i,r=p[i]+i;
		}
		ans+=(p[i]==0?0:(p[i]-1)/2);
//		cout<<i<<' '<<p[i]<<' '<<c<<' '<<r<<' '<<ans<<endl;
	}
//	for (int i=1;i<m-1;++i) cout<<p[i]<<' ';
//	cout<<endl;
	cout<<ans;
	return 0;
}

最长双回文串

开始有难度了......

我们会发现，当我们跑ManacherManacher时所添加的'#'正好是分割双回文串的工具，所以我们维护一个LiL_i表示以ii为左边界，向右的最长回文串，RiR_i反之，每次跑出一个pip_i顺带更新。

当然这还没结束，因为跑ManacherManacher只能处理最大边界，那内部的咋办？

观察回文串的性质，以LiL_i为例，如果往右缩小22格，回文串的长度−2-2，RiR_i方向与之相反，这样我们就处理完所有LiL_i和RiR_i。

最后Ans=maxi=3len−2Li+RiAns=max_{i=3}^{len-2} {L_i+R_i}即可（显然11和lenlen不能当分割，因为左/右两边没有合法串）。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	void Main() {
		string S;
		cin >> S;
		int n = S.size(), k = 0;
		vec<char> s((n << 1) +5);
		s[k] = '^', s[++k] = '#';
		for (char c : S) {
			s[++k] = c;
			s[++k] = '#';
		}
		s[k + 1] = '$';
		int c = 0, R = 0;
		vec<int> p(k + 5, 0);
		vec<int> l(k + 5, 0), r(k + 5, 0);
//		for (int i=1;i<=k;++i) cout<<s[i];
//		cout<<endl;
		for (int i = 1; i <= k; ++i) {
			if (i < R) {
				int j = 2 * c - i;
				p[i] = min(p[j], R - i);
			} else p[i] = 1;
			while (s[i + p[i]] == s[i - p[i]]) ++p[i];
			if (i + p[i] > R) {
				c = i, R = i + p[i];
			}
			l[i - p[i] + 1] = max(l[i - p[i] + 1], p[i] - 1);
			r[i + p[i] - 1] = max(r[i + p[i] - 1], p[i] - 1);
		}
//		for (int i=1;i<=k;++i) cout<<p[i]<<' ';
//		cout<<endl;
//		for (int i=1;i<=k;++i) cout<<l[i]<<' '<<r[i]<<endl;
		for (int i = 3; i <= k; i += 2) l[i] = max(l[i], l[i - 2] - 2);
		for (int i = k; i >= 3; i -= 2) r[i] = max(r[i], r[i + 2] - 2);
		int ans = 0;
//		for (int i=1;i<=k;++i) cout<<l[i]<<' '<<r[i]<<endl;
		for (int i = 3; i <= k - 2; ++i) ans = max(ans, l[i] + r[i]);
		cout << ans;
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

ACAM

被迫先去写计算几何（悲

PAM

被迫先去写计算几何（悲

SA

被迫先去写计算几何（悲

（为什么没有SAMSAM呢，那当然是我不会啦！）

userId_undefined
去预览
0/2000

全部评论 16

  • userId_undefined
    Asdfre
    时空双修者
    置顶

    大佬们/bx

    2026-07-30 来自 广东

    1
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    /bx

    2026-08-03 来自 浙江

    1
  • userId_undefined
    Xylophone
    传道者

    你咋这强你咋这强你咋这强你咋这强你咋这强你咋这强你咋这强你咋这强你咋这强

    2026-08-03 来自 广东

    1
  • userId_undefined
    Xylophone
    传道者

    Hash 本质上是一种由雌性大麻植物花蕊中的树脂提炼、浓缩而成的非法毒品。其核心特征在于四氢大麻酚（THC）含量极高，是一种毒性强烈的致幻剂。在中国法律框架下，Hash 及其所有相关制品被明确定义为毒品，其生产、销售、携带和吸食均属严重违法行为。

    2026-08-02 来自 广东

    1
    • userId_undefined
      Asdfre
      回复
      Xylophone

      以严肃吓哭

      2026-08-02 来自 广东

      0
    • userId_undefined
      🥥
      回复
      Xylophone

      Hash 本质上是一种由雌性大麻植物花蕊中的树脂提炼、浓缩而成的非法毒品。其核心特征在于四氢大麻酚（THC）含量极高，是一种毒性强烈的致幻剂。在中国法律框架下，Hash 及其所有相关制品被明确定义为毒品，其生产、销售、携带和吸食均属严重违法行为。

      2026-08-02 来自 上海

      0
    • userId_undefined
      cjdst
      回复
      Xylophone

      吓哭了

      2026-08-02 来自 浙江

      0
  • userId_undefined
    🥥
    尊贵铂金

    字符串不比计算几何好玩多了

    2026-07-31 来自 上海

    1
  • userId_undefined
    🥥
    尊贵铂金

    羡慕会ACAM羡慕会PAM羡慕会SA我咋啥都不会/kel

    2026-07-31 来自 上海

    1
  • userId_undefined
    🥥
    尊贵铂金

    /bx 别思考，我在吵

    2026-07-31 来自 上海

    1
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    为何是 ≤21\le 21 个串不是 ≤11\le 11

    2026-07-31 来自 广东

    1
    • userId_undefined
      Asdfre
      回复
      cjdst

      因为最多有10个通配符，11个纯字符串，加起来就是21个TokenToken

      2026-07-31 来自 广东

      0
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    羡慕会KMP羡慕会ACAM羡慕会PAM羡慕会SA我咋啥都不会/kel

    2026-07-31 来自 广东

    1
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    太多了，这几天一定写完！

    2026-07-31 来自 广东

    1
  • userId_undefined
    Eucatastrophe‌
    禁言
    GESP6级

    串 串 大 合 集

    2026-07-30 来自 浙江

    1
  • userId_undefined
    wcqk
    禁言
    出题人

    555 orz

    2026-07-30 来自 湖北

    1
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    CF580E有了这个结论是不是可以 KMP 做

    2026-08-01 来自 广东

    0
    • userId_undefined
      Asdfre
      回复
      cjdst

      emmm，那线段树维护的是什么？还是说你有其他方法处理带修？

      2026-08-01 来自 广东

      0
    • userId_undefined
      cjdst
      回复
      Asdfre

      带修吗，不早说（（（

      2026-08-01 来自 浙江

      0
    • userId_undefined
      Asdfre
      回复
      cjdst

      beng

      2026-08-01 来自 广东

      0
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    为何是 ≤21\le 21 个串不是 ≤11\le 11

    2026-07-31 来自 广东

    0
  • userId_undefined
    Asdfre
    时空双修者

    @cjdst

    2026-07-30 来自 广东

    0
    • userId_undefined
      Asdfre
      回复
      Asdfre

      等会我通配符代码是不是没写（雾

      2026-07-30 来自 广东

      0
  • userId_undefined
    Asdfre
    时空双修者

    d

    2026-07-30 来自 广东

    0

热门讨论