制糊串整理（持续更新ing）
发现字符串部分真的是空白啊！
那就从头开始吧
目录（刚考完合格考，终于有时间了qwq）
Manacher算法
找回文串的，大家都知道。
然后注意一点就是这个只能找到长度为奇数的回文串，所以我们得在两个字符之间补充一个字符，最前面也需要补充一个字符。
Manacher原理就是利用他的对称性，如果一个大的串对称，那么如果前半部分有回文串，后半部分相应位置也应该有。
注意到时间复杂度跟暴力扩展判断的次数有关，每次扩展都会使得\(r+1\)，显然复杂度是线性的。
cin>>(s+1);
int len=strlen(s+1);
t[0]='!';
t[++tot]='&';
for(int i=1;i<=len;i++) t[++tot]=s[i],t[++tot]='&';
t[++tot]='%';
for(int i=1,r=0,d=0;i<=tot;i++){
if(i>r) p[i]=1;else p[i]=min(p[2*d-i],r-i+1);
while(t[i+p[i]]==t[i-p[i]]) p[i]++;
if(i+p[i]-1>r) r=i+p[i]-1,d=i;
}
来几个例题吧
P4555 [国家集训队] 最长双回文串
处理出来以每个位置结尾，开头的最长回文串长度，然后求个\(max(ed_i+st_{i+1})\)就完事了
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,a,n) for(int i=n;i>=a;--i)
#define N(x,y) ((int)((int)(x##e##y)+5))
using namespace std;
char s[N(6,5)],t[N(6,5)];
int n,m;
int p[N(6,5)],l[N(6,5)],r[N(6,5)];
signed main(){
cin>>(s+1);
t[0]='!';
n=strlen((s+1));
t[m=1]='@';
rep(i,1,n)t[++m]=s[i],t[++m]='@';
t[++m]='&';
int d=0,rr=0;
rep(i,1,m){
if(i>rr) p[i]=1;else p[i]=min(rr-i+1,p[2*d-i]);
while(t[i+p[i]]==t[i-p[i]]) p[i]++;
if(i+p[i]-1>rr){
rep(j,rr+1,i+p[i]-1){
if(j%2==0)l[j>>1]=j-i+1;
}
rr=i+p[i]-1,d=i;
}
}
d=0,rr=m;
per(i,1,m-1){
if(i<rr) p[i]=1;else p[i]=min(i-rr+1,p[2*d-i]);
while(t[i+p[i]]==t[i-p[i]]) p[i]++;
if(i-p[i]+1<rr){
rep(j,i-p[i]+1,rr-1){
if(j%2==0)r[j>>1]=i-j+1;
}
rr=i-p[i]+1,d=i;
}
}
int ans=0;
rep(i,1,n-1){
ans=max(ans,l[i]+r[i+1]);
}
cout<<ans;
return 0;
}
P1659 [国家集训队] 拉拉队排练
属于\([1,p_i-1]\)的所有回文长度都存在，所以直接进行差分，最后对每一种长度的个数快速幂计算一下即可。
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,a,n) for(int i=n;i>=a;--i)
#define N(x,y) ((int)((int)(x##e##y)+5))
#define i64 long long
using namespace std;
inline i64 read(){
i64 x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int mod=19930726;
i64 qpow(int a,int b){
i64 res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
char s[N(2,6)],t[N(2,6)];
i64 n,m,k;
i64 p[N(1,6)],buk[N(1,6)];
signed main(){
n=read(),k=read();
cin>>(s+1);
n=strlen((s+1));
s[0]='!';
int d=0,rr=0;
rep(i,1,n){
if(i>rr) p[i]=1;else p[i]=min(1ll*(rr-i+1),p[2*d-i]);
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
buk[1]++,buk[2*p[i]+1]--;
if(i+p[i]-1>rr){
rr=i+p[i]-1,d=i;
}
}
int mx=0;
rep(i,1,n){
buk[i]+=buk[i-1];
if(buk[i]){
mx=max(mx,i);
}
}
i64 ans=1;
i64 pt=mx;
while(k){
if(k<=0||pt<=0) break;
if(pt%2==0) {pt--;continue;}
ans=1ll*ans*qpow(pt,min(buk[pt],k))%mod;
k-=min(buk[pt],k);
pt--;
}
cout<<ans;
return 0;
}
P5446 [THUPC2018] 绿绿和串串
首先以\(n\)结尾的回文串都合法，然后所有结尾位置为一个合法位置且以\(1\)开头的回文串也都合法，然后就从后往前扫依次判断就好了。
#include<bits/stdc++.h>
#define i64 long long
using namespace std;
int n,p[5000005],vis[5000005];
void solve(){
string a;
cin>>a;
a.push_back('!');
reverse(a.begin(),a.end());
n=(int)a.size()-1;
for(int i=1;i<=n;i++){
vis[i]=0;
}
for(int i=1,d=0,r=0;i<=n;i++){
if(i>r) p[i]=1; else p[i]=min(p[2*d-i],r-i+1);
while(a[i+p[i]]==a[i-p[i]]) p[i]++;
if(i+p[i]-1>r) r=i+p[i]-1,d=i;
}
for(int i=1;i<=n;i++){
if(i-p[i]+1==1)vis[i]=1;
if(i+p[i]-1==n&&vis[2*i-n]) vis[i]=1;
}
for(int i=n;i>=1;i--){
if(vis[i]) cout<<n-i+1<<" ";
}
putchar(10);
}
signed main(){
int tt;
tt=read();
while(tt--){
solve();
}
}
Pass
后缀数组
这玩意我以前都是纯靠背的/kk
写几个定义吧。
\(su_i\)代表以\(i\)开头的后缀。\(rk_i\)代表\(su_i\)在所有后缀中的排名。\(sa_i\)代表排名为\(i\)的后缀的起始位置，也就是说\(sa_{rk_i}=rk_{sa_i}=i\)。
然后 我们要求的就是\(sa\)数组。
我们可以通过\(2^{w-1}\)级子串的排名\(rk_i\)来推出\(2^w\)级子串的\(sa_i\)，我们通过比较\((rk_i,rk_{i+2^{w-1}})\)和\((rk_j,rk_{j+2^{w-1}})\)，就可以确定新的\(rk_i\)和\(rk_j\)。
其实有一个常数的优化就是，那些后面不全的后缀，他们比较的时候一定是排在最前面的。
signed main(){
cin>>(s+1);
int m=1<<7,p=0,n=strlen(s+1);
for(int i=1;i<=n;i++) buk[rk[i]=s[i]]++,id[rk[i]]=1;
for(int i=1;i<=m;i++) buk[i]+=buk[i-1],id[i]+=id[i-1];
for(int i=n;i;i--) sa[buk[s[i]]--]=i;
for(int i=1;i<=n;i++) rk[i]=id[s[i]];
for(int w=1;w<=n&&rk[sa[n]]<n;w<<=1,p=0){
for(int i=n-w+1;i<=n;i++) id[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w;
for(int i=1;i<=n;i++) buk[rk[sa[i]]]=i;
for(int i=n;i;i--) sa[buk[rk[id[i]]]--]=id[i];
for(int i=1;i<=n;i++) id[sa[i]]=id[sa[i-1]]+((rk[sa[i]]!=rk[sa[i-1]])||(rk[sa[i]+w]!=rk[sa[i-1]+w]));
for(int i=1;i<=n;i++) rk[i]=id[i];
}
for(int i=1;i<=n;i++){
cout<<sa[i]<<" ";
}
return 0;
}
刚开始有点看不懂，感觉有几点需要说明一下：
- 为啥是\(sa_i>w\)的时候把\(sa_i-w\)放进去，因为就是相当于把当前这个位置作为第二关键字、它所对应的第一关键字的位置给放进去了（因为你基数排序只比较第一个关键字，\(id\)放进去的时候要按照第二关键字先排好序了）
- 没必要一定要让\(w\)跑满，只要\(rk_{sa_n}=n\)了就说明已经排完序了
然后这里再来一个定义\(ht_i\)代表\(|lcp(su_{sa_i},su_{sa_{i-1}})|\)，特别地，有\(ht_1=0\)。
然后有一个性质：$ht_{rk_i}\geq ht_{rk_{i-1}}+1 $
标签：rr,int,++,i64,整理,字符串,sa,rk From： https://www.cnblogs.com/longscatterer/p/zi-fu-chuan-ke-ai-miao.html