给出一个数字，求在其中两位之间插入一个加号后得到的答案末尾$0$最多的个数。

题解：
第二个数的末尾就是原串的末尾，所以如果需要和第一个数加起来末尾为$0$，那么从后往前扫，第二个数为$0$的位在不进位的情况下第一个数的对应位需要是$0$，不为$0$的位的对应位$x$应该是$10 - x$，然后开启进位模式所有数的对应位都是$9-x$，然后求一个原串和转换后的串的最长公共前缀即可得出答案，可以写$\rm exkmp$
$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 1000006
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define mod 998244353
#define S 131
#define LL long long
using namespace std;char s[maxn],s0[maxn];
LL hs[2][maxn],pw[maxn];
int n;LL calc(int a,int b,LL *hs){ return ((hs[b] - hs[a-1] * pw[b-a+1]) % mod + mod) % mod; }int main(){pw[0] = 1;rep(i,1,maxn-1) pw[i] = pw[i-1] * S % mod;while(scanf("%s",s+1)!=EOF){n = strlen(s+1);rep(i,1,n) hs[0][i] = (hs[0][i-1] * S + s[i]) % mod , s0[i] = s[i]; int i;for(i=n;i>=1 && s[i] == '0';i--);s[i] = (10 - (s[i] - '0')) + '0';int t = i;per(j,i-1,1) s[j] = (9 - (s[j] - '0')) + '0';rep(i,1,n) hs[1][i] = (hs[1][i-1] * S + s[i]) % mod;int ans = 0;rep(i,1,n-1){int L = 0 , R = min(i , n-i) , mid;for(;L<R;){mid = L+R+1 >> 1;if(calc(i-mid+1,i,hs[0]) == calc(n-mid+1,n,hs[1]))L = mid;else R = mid - 1;}if(i <= t){while(n-L <= i && s0[i-L] == '9') L++;while(i-L <= 0 && n-L > i && s0[n-L] == '9') L++;}else{while(n-L <= i && s0[i-L] == '0') L++;while(i-L <= 0 && n-L > i &&s0[n-L] == '0') L++;}ans = max(ans , L);}printf("%d\n",ans);}
}

题意：单点修改$S$中的一个字符，求$S[l...r]$中$T$的出现次数，$|S| , \sum|T| \leq 1e5，\rm Timelimit \ 6s$

太离谱了。
考虑到这是$\rm CF$的$\rm 6s$，我们用$\rm bitset\ C[i][j]$代表字符$i$在位置$j$是否出现。
则求出$ret = \operatorname{and}_{i=0}^{|T|-1} C[T_i]>>i$后取$ret$在$[l,r-|T|+1]$中的$1$的个数即可。
时间复杂度$O(\frac {n^2}{\omega})$无压力水过
其实可以分块一下得到更科学的复杂度：
对于长度大于块大小$S$的字符串我们暴力$\rm kmp$,$O(\frac {n^2}S)$
对于长度小于块大小$S$的字符串我们分它是在一个块内还是跨两个块来考虑。
对于块内的答案直接分块求块内的$\rm bitset$即可做到$O(\frac {nS}{\omega})$
对于跨两个块的答案直接对于$\frac nS$个交界处前后$|T|$个字符拿出来跑$\rm kmp$，$O(\frac {n|T|}S)$，总复杂度还是$O(\frac {n^2}S)$
所以$S = \sqrt {\omega n}$时最快，为$O(\frac {n\sqrt n}{\sqrt \omega})$

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 100005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
using namespace std;char s[maxn],ch[maxn];
int Q,n;bitset<maxn>C[26];int main(){scanf("%s",s+1);n = strlen(s+1);rep(i,1,n) C[s[i] - 'a'][i] = 1;scanf("%d",&Q);for(int op,l,r;Q--;){scanf("%d%d",&op,&l);if(op == 1){scanf("%s",ch);C[s[l]-'a'][l] = 0;C[(s[l]=ch[0])-'a'][l] = 1;}else{scanf("%d%s",&r,ch);int t = strlen(ch);static bitset<maxn>ans;ans.set();rep(i,0,t-1)ans &= (C[ch[i] - 'a'] >> i);r -= t - 1;ans <<= maxn - 1 - r;ans >>= maxn - 1 - r + l;printf("%d\n",ans.count());}}
}

$O(\frac {n\sqrt n}{\sqrt w})$做法：（实际上没有快多少）

#include<bits/stdc++.h>
#define maxn 100005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
#define S 1800
using namespace std;char s[maxn],ch[maxn];
int Q,n,id[maxn],st[maxn],ed[maxn],nxt[maxn],m;bitset<S>C[26][maxn/S+5];int kmp(int l,int r){int ans = 0;for(int i=l,j=0;i<=r;i++){while(j != -1 && ch[j] != s[i]) j = nxt[j];if(++j == m) ans ++;}return ans;
}int solve(int b,int l,int r){static bitset<S>ans;ans.set();rep(i,0,m-1) ans &= C[ch[i]-'a'][b] >> i;r -= m - 1;ans <<= S - 1 - r;ans >>= S - 1 - r + l;return ans.count();
}int main(){scanf("%s",s+1);n = strlen(s+1);rep(i,1,n) id[i] = i / S , st[id[i]] = st[id[i]] ? st[id[i]] : i , ed[id[i]] = i;rep(i,1,n) C[s[i]-'a'][id[i]][i - st[id[i]]] = 1;scanf("%d",&Q);for(int op,l,r;Q--;){scanf("%d%d",&op,&l);if(op == 1){scanf("%s",ch);C[s[l]-'a'][id[l]][l - st[id[l]]] = 0;C[(s[l]=ch[0])-'a'][id[l]][l - st[id[l]]] = 1;}else{scanf("%d%s",&r,ch);m = strlen(ch);nxt[0] = -1;for(int j=-1,k=0;k<m;)if(j == -1 || ch[j] == ch[k]) nxt[++k] = ++j;else j = nxt[j];int ans = 0;if(m >= S) ans = kmp(l,r);else{rep(i,id[l],id[r]) ans += solve(i,max(l-st[i],0),min(r-st[i],ed[i]-st[i]));rep(i,id[l],id[r]-1) ans += kmp(max(l,ed[i]-m+2),min(ed[i]+m-1,r));}printf("%d\n",ans);}}
}

UPD:完全错了，后一种做法还是$O(\frac {n^2}{\omega})$的，根号做法还是推荐分块维护后缀自动机加$\rm kmp$。

在加入$t$的时候随便维护一下每个字母的最长相同字母连续子序列即可。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 1000006
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
using namespace std;char s[maxn];
int n,m;
LL f[26];int main(){scanf("%d",&n);for(;n--;){scanf("%s",s);m = strlen(s);vector<pair<int,int> >G;for(int i=0,j;i<m;i=j){for(j=i;j < m && s[i] == s[j];j++);G.push_back(make_pair(s[i]-'a' , j-i));}if(G.size() == 1){rep(i,0,25) if(i ^ G[0].first) f[i] = min(f[i] , 1ll);f[G[0].first] = min(f[G[0].first] + (f[G[0].first] + 1ll) * G[0].second , (LL)1e11);}else{rep(i,0,25) f[i] = min(f[i] , 1ll);if(G[0].first == G.back().first) f[G[0].first] += G[0].second + G.back().second;else{f[G[0].first] += G[0].second;f[G.back().first] += G.back().second;} rep(i,0,G.size()-1) f[G[i].first] = max(f[G[i].first] , G[i].second * 1ll);} }LL ans = 0;rep(i,0,25) ans = max(ans , f[i]);printf("%d\n",ans);
}

给定一个长度为$n$的括号串，问有多少种不同的合法的本质不同的括号子串。

一边插入字符建出$SAM$，一边对于新出现的节点套个$map$统计新节点所代表的串中有几个合法的括号串。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 500005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long 
using namespace std;int n;
char s[maxn];
map<int,int>P[maxn];
int fa[maxn<<1],last,len[maxn<<1],tr[maxn<<1][2],tot;
void ins(int c){int u = ++tot , p = last , q;len[last = u] = len[p] + 1;for(;p!=-1 && !tr[p][c];p=fa[p]) tr[p][c] = u;if(p == -1) fa[u] = 0;else if(len[q = tr[p][c]] == len[p] + 1) fa[u] = q;else{int v = ++tot;memcpy(tr[v],tr[q],sizeof tr[q]),fa[v]=fa[q],len[v]=len[p]+1;for(;p!=-1 && tr[p][c] == q;p=fa[p]) tr[p][c] = v;fa[q] = fa[u] = v;}
}int main(){scanf("%d%s",&n,s+1);rep(i,0,n) P[i][0] = 0;stack<int>sta;LL ans = 0;fa[0] = -1;rep(i,1,n){ins(s[i] == '(' ? 0 : 1);if(s[i] == '(')sta.push(i);else{if(sta.empty()) P[0].clear(),P[0][0] = 0;else{int u = sta.top() , pr;sta.pop();if(sta.empty()) pr = 0;else pr = sta.top();int t = (*P[pr].rbegin()).second + 1;P[pr][u] = t;map<int,int>::iterator it = P[pr].lower_bound(i - len[fa[last]] + 1);it--;ans += (*it).second;}}}printf("%lld\n",ans);
} 

字符集为前$k$个小写字母，给出一个长度为$n \leq 200000$的字符串$S$，有$Q \leq 20000$次操作，有两种操作，一种是将$S[l,r]$赋值为字符$c$，一种是给出$k$个小写字母的一个排列作为字符串$T$，询问往$S$中插入字符后成为$T$循环$p$次后，求最小的$p$。

水题，线段树随便维护一下连续两个字符为$ab$的方案数，那么对于给出的排列，$a$的位置$>$$b$的位置则答案增加$ab$的方案数。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 200005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long 
#define lc u<<1
#define rc lc|1
using namespace std;int n,m,K;
int tr[maxn<<2][10][10],tag[maxn<<2],len[maxn<<2],pl[maxn<<2],pr[maxn<<2];
char ch[maxn],s[maxn];void dtp(int u,int p){memset(tr[u],0,sizeof tr[u]);tr[u][p][p] = len[u]-1;pl[u] = pr[u] = p;tag[u] = p;
}void dt(int u){if(tag[u] != -1){dtp(lc,tag[u]);dtp(rc,tag[u]);tag[u] = -1;}
}void upd(int u){rep(i,0,K-1) rep(j,0,K-1) tr[u][i][j] = tr[lc][i][j] + tr[rc][i][j];tr[u][pr[lc]][pl[rc]] ++;pl[u] = pl[lc] , pr[u] = pr[rc];
}void Build(int u,int l,int r){len[u] = r-l+1;if(l==r) return (void)(pl[u]=pr[u]=s[l]-'a');int m=l+r>>1;Build(lc,l,m),Build(rc,m+1,r);upd(u);
}void ins(int u,int l,int r,int ql,int qr,int p){if(l>qr||ql>r) return ;if(ql<=l&&r<=qr) return (void)(dtp(u,p));int m=l+r>>1;dt(u);ins(lc,l,m,ql,qr,p) , ins(rc,m+1,r,ql,qr,p);upd(u);
}int main(){memset(tag,-1,sizeof tag);scanf("%d%d%d",&n,&m,&K);scanf("%s",s+1);Build(1,1,n);for(int op,l,r,c;m--;){scanf("%d",&op);if(op == 1){scanf("%d%d%s",&l,&r,&ch);ins(1,1,n,l,r,ch[0]-'a');}else{scanf("%s",ch);static int p[11]={};int ans = 1;rep(i,0,K-1) rep(j,0,i)ans += tr[1][ch[i]-'a'][ch[j]-'a'];printf("%d\n",ans);}}
} 

写$hash$实现$O(n\log^2n)$后缀排序后就是一个求$l\leq i \leq r , x \leq (i \bmod k) \leq y$的$rmq$问题。
对于这$\bmod k$，
我们分$k \leq S$，则离线后处理$k$相等的所有询问，对于$i \bmod k$相同的所有$i$写一个$RMQ$。
总复杂度$O(Sn\log n)$
$k \gt S$，则暴力找所有的$x+jk \leq i \leq y + jk$的区间，复杂度$O(\frac {n^2}S)$。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 100005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
#define pb push_back
#define Ct const
#define mod 998244353
using namespace std;char s[maxn],t[maxn];
int q,ls,lt,c[maxn],rk[maxn];
LL pw[maxn],hst[maxn],hs[maxn];LL calc(int u,int l){if(l <= u) return hs[l];if(l <= u + lt) return (hs[u] * pw[l-u] + hst[l-u]) % mod;return ((hs[u] * pw[l-u] + hst[lt] * pw[l-u-lt] + hs[l-lt] - hs[u] * pw[l-lt-u]) % mod + mod) % mod;
}int getc(int u,int l){if(l <= u) return s[l];if(l <= u + lt) return t[l-u];return s[l-lt];
}bool cmp(Ct int &u,Ct int &v){int L = 0 , R = ls + lt , mid;for(;L<R;){mid = L+R+1 >> 1;if(calc(u,mid) == calc(v,mid)) L = mid;else R = mid - 1;}return getc(u,L+1) < getc(v,L+1);
}#define vc vector
#define vi vector<int>
#define lim 17
#define S 100int L[maxn],R[maxn],K[maxn],X[maxn],Y[maxn],lg[maxn],ans[maxn];
vi G[maxn];vc<vi>st;bool cmp2(Ct int &u,Ct int &v){ if(rk[u] < rk[v] || (rk[u] == rk[v] && u < v)) return 1;return 0; }
int qry(int u,int v){if(u > v) return ls+1;int t = lg[v-u+1];return cmp2(st[t][u],st[t][v-(1<<t)+1]) ? st[t][u] : st[t][v-(1<<t)+1];
}int main(){scanf("%s%s%d",s+1,t+1,&q);ls = strlen(s+1);lt = strlen(t+1);rep(i,1,ls) hs[i] = (hs[i-1] * S + s[i]) % mod;rep(i,1,lt) hst[i] = (hst[i-1] * S + t[i]) % mod;pw[0] = 1;rep(i,1,ls+lt) pw[i] = pw[i-1] * S % mod; rep(i,0,ls) c[i] = i;sort(c,c+ls+1,cmp);int cnt = 0;rep(i,0,ls)if(i == 0 || cmp(c[i-1],c[i]))rk[c[i]] = ++cnt;else rk[c[i]] = cnt;st=vc<vi>(lim,vi(ls+1));rep(i,0,ls) st[0][i] = i;rep(j,1,lim-1) rep(i,0,ls-(1<<j)+1)st[j][i] = cmp2(st[j-1][i],st[j-1][i+(1<<j-1)]) ? st[j-1][i] : st[j-1][i+(1<<j-1)];rep(i,2,ls) lg[i] = lg[i>>1] + 1;rk[ls+1] = 0x3f3f3f3f;rep(i,1,q){	scanf("%d%d%d%d%d",&L[i],&R[i],&K[i],&X[i],&Y[i]);ans[i] = ls+1;if(K[i] <= S) G[K[i]].pb(i);else{for(int j=0;j*K[i]+X[i]<=ls;j++)if(j*K[i]+X[i] <= R[i] && j*K[i]+Y[i] >= L[i]){int t = qry(max(j*K[i]+X[i],L[i]),min(j*K[i]+Y[i],R[i]));if(cmp2(t,ans[i])) ans[i] = t;}}}rep(i,1,S) rep(j,0,i-1){st=vc<vi>(lim,vi(ls / i + 5));int len;for(len=0;i*len+j<=ls;len++) st[0][len] = i*len+j;rep(k,1,lim-1) rep(p,0,len-(1<<k)+1) st[k][p] = cmp2(st[k-1][p],st[k-1][p+(1<<k-1)]) ? st[k-1][p] : st[k-1][p+(1<<k-1)];for(int v:G[i]) if(X[v] <= j && j <= Y[v]){int t = qry((int)ceil((1.0 * L[v]-j) / i) , (int)floor((1.0 * R[v] - j) / i));if(cmp2(t , ans[v]))ans[v] = t;}}rep(i,1,q) if(ans[i] == ls+1) ans[i] = -1;rep(i,1,q)printf("%d%c",ans[i]," \n"[i==q]);
}

有$n$个字符串$s[1..n]$和$q$次操作,每次操作是$1\ l\ r$表示询问区间$[l,r]$的所有子区间$[a,b]$中，$\operatorname{lcp}(s[a],s[a+1],…,s[b])\times(b-a+1)$的最大值。 $2\ x\ str$表示把第$x$个字符串改成$str$。$n,q\leq 1e5$。

容易发现$\operatorname{lcp}(s[a],s[a+1],…,s[b])$和$b-a+1$其中必有一个的最大值不会大于$\sqrt n$，因为如果$b-a+1 > \sqrt n$，则$s_i$的长度不可能都$\gt \sqrt n$，所以$\operatorname{lcp}(s[a],s[a+1],…,s[b]) \leq \sqrt n$。
所以就维护相邻两个字符串的$lcp$数组，若$b-a+1 < \sqrt n$则直接按$lcp$从大到小插入维护。
否则就对于$1...\sqrt n$每个维护一个线段树维护区间最长为$1$的连续子段即可。

还是分块，我吐了。
对于长度$> \sqrt L$的建出$s_k$的$AC$自动机后暴力查询$s_l ... s_r$的子树和。
对于长度$\leq \sqrt L$的离线在$AC$自动机从$s_1$加到$s_n$，然后$O(|s_k|)$在$AC$自动机上查询的父亲和，注意修改数是$O(n)$，查询数是$O(n \sqrt n)$，可以用分块维护前缀和得到$O(n \sqrt n)$的复杂度。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 100005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define pb push_back
#define LL long long 
#define S 305
using namespace std;int n,Q;
string s[maxn];
int L[maxn],R[maxn],K[maxn];
LL ans[maxn];
vector<int>in[maxn],ot[maxn],G[maxn<<1];#define maxc 26
LL sm[maxn];
int last,fa[maxn<<1],tr[maxn<<1][maxc],len[maxn<<1],tot,f[maxn<<1],sa[maxn<<1],c[maxn<<1],pos[maxn];
void ins(int c){if(tr[last][c]){int p = last , q;if(len[q = tr[p][c]] != len[p] + 1){int v = ++tot;memcpy(tr[v],tr[q],sizeof tr[q]),fa[v] =fa[q] , len[v] = len[p] + 1;for(;p != -1 && tr[p][c] == q;p=fa[p]) tr[p][c] = v;fa[q] = v;}last = tr[last][c];return;}int u = ++tot , p = last , q;len[last = u] = len[p] + 1;for(;p!=-1 && tr[p][c]==0;p=fa[p]) tr[p][c]=u;if(p == -1) fa[u] = 0;else if(len[q=tr[p][c]] == len[p] + 1) fa[u] = q;else{int v = ++tot;memcpy(tr[v],tr[q],sizeof tr[q]),fa[v] =fa[q] , len[v] = len[p] + 1;for(;p != -1 && tr[p][c] == q;p=fa[p]) tr[p][c] = v;fa[q] = fa[u] = v;}
}int st[maxn<<1],ed[maxn<<1],tim,ST[maxn<<1],ED[maxn<<1];void dfs0(int u){st[u] = ++tim;for(int v:G[u]) dfs0(v);ed[u] = tim;
}int bl[maxn],sb[maxn<<1],id[maxn<<1];
int main(){ios::sync_with_stdio(false);cin >> n >> Q;rep(i,1,n) cin>>s[i];rep(i,1,Q){cin >> L[i] >> R[i] >> K[i];if(s[K[i]].length() <= S) ot[R[i]].pb(i),in[L[i]-1].pb(i);else G[K[i]].pb(i);}rep(i,1,n) if(!G[i].empty()){last = 0 , fa[0] = -1;rep(j,0,s[i].length()-1) ins(s[i][j]-'a'),f[last]++;rep(j,0,tot) c[j] = 0;rep(j,0,tot) c[len[j]]++;rep(j,1,tot) c[j] += c[j-1]; rep(j,0,tot) sa[--c[len[j]]] = j;per(j,tot,1){int u = sa[j];f[fa[u]] += f[u];}rep(j,1,n){int u = 0 , L = 0;rep(k,0,s[j].length()-1){int v = s[j][k] - 'a';for(;u != -1 && !tr[u][v];u=fa[u]);if(u == -1) u = 0 , L = 0;else L = min(L + 1 , len[u] + 1) , u = tr[u][v];}sm[j] = sm[j-1] + (L == s[j].length()) * (f[u]);}for(int v:G[i])ans[v] = sm[R[v]] - sm[L[v]-1];G[i].clear();memset(tr,0,sizeof (tr[0]) * (tot+1));rep(j,0,tot) f[j] = 0;tot = 0;}last = 0;fa[0] = -1;rep(i,1,n){last = 0;rep(j,0,s[i].length()-1) ins(s[i][j]-'a');pos[i] = last;}rep(i,1,tot) G[fa[i]].pb(i);dfs0(0);rep(i,1,tim) id[i] = i / S , ST[id[i]] = ST[id[i]] ? ST[id[i]] : i , ED[id[i]] = i;;rep(i,1,n){int u = st[pos[i]] , v = ed[pos[i]];rep(j,id[u]+1,id[v]-1) bl[j] ++;if(id[u] == id[v]){rep(j,u,v) sb[j]++;}else{rep(j,u,ED[id[u]]) sb[j]++;rep(j,ST[id[v]],v) sb[j]++;}for(int p:in[i]){int u = 0 , t = K[p];rep(j,0,s[t].length()-1){v = s[t][j] - 'a';for(;u != -1 && !tr[u][v];u = fa[u]);if(u == -1) u = 0;else u = tr[u][v];ans[p] -= sb[st[u]] + bl[id[st[u]]]; }}for(int p:ot[i]){int u = 0 , t = K[p];rep(j,0,s[t].length()-1){v = s[t][j] - 'a';for(;u != -1 && !tr[u][v];u = fa[u]);if(u == -1) u = 0;else u = tr[u][v];ans[p] += sb[st[u]] + bl[id[st[u]]]; }}}rep(i,1,Q) printf("%lld\n",ans[i]);
}

给一棵树，每条边上有一个字符，求有多少对 $(x,y)(x<y)$，满足$x$到$y$路径上的边上的字符按顺序组成的字符串为回文串。

题解：
点分治，然后回文串分为两部分$S$和$T+S$，其中$T$是$T+S$的一个回文前缀，所以我们建出$AC$自动机，同时用$hash$判断每个前缀是否是回文前缀。
算了太毒了。