扩展kmp与回文串问题
在扩展kmp中,设模式串为P1,目标串为P2
extend[i]表示P2[i]~P2[n]与P1的最长公共前缀长度.
设原串为P,将其倒置为S.
以P为模式串执行一遍e-KMP,得到extend1数组,P的前缀是回文串的条件是extend1[i]+i=length(S)
以S为模式串执行一遍e-KMP,得到extend2数组,P的后缀是回文串的条件是extend2[i]+i=length(P)
画出图更好理解.
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int Next[500001];
int extend1[500010];
int extend2[500010];
char p[500001];
char s[500001];
int value[500001];
void eKMP_pre(char x[],int m,int next[]){
next[0]=m;
int j=0;
while(j+1<m&&x[j]==x[j+1]) j++;
next[1]=j;
int k=1;
for(int i=2;i<m;++i){
int p=next[k]+k-1;
int L=next[i-k];
if(i+L-1<p) next[i]=L;
else{
j=max(0,p-i+1);
while(i+j<m&&x[i+j]==x[j]) j++;
next[i]=j;
k=i;
}
}
}
void eKMP(char x[],int m,char y[],int n,int next[],int extend[]){
eKMP_pre(x,m,next);
int j=0;
while(j<n&&j<m&&x[j]==y[j]) j++;
extend[0]=j;
int k=0;
for(int i=1;i<n;++i){
int p=extend[k]+k-1;
int L=next[i-k];
if(i+L-1<p) extend[i]=L;
else{
j=max(0,p-i+1);
while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
extend[i]=j;
k=i;
}
}
}
int v[26];
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int kase=0;
int n,T;
scanf("%d",&T);
while(T--){
for(int i=0;i<26;++i){
scanf("%d",&v[i]);
}
scanf("%s",p);
int len=strlen(p);
int k=0;
for(int i=len-1;i>=0;i--){
s[k]=p[i];
value[k]=v[s[k]-'a'];
if(k) value[k]=value[k]+value[k-1];
k++;
}
eKMP(p,len,s,len,Next,extend1);
eKMP(s,len,p,len,Next,extend2);
int ans=-INF;
for(int i=1;i<len;++i){
int temp=0;
if(i+extend1[i]==len){
temp+=value[i+extend1[i]-1]-value[i-1];
if(extend1[i]+extend2[extend1[i]]==len){
temp+=value[i-1];
}
}
else{
if(len-i+extend2[len-i]==len){
temp+=value[i-1];
}
}
ans=max(ans,temp);
}
printf("%d\n",ans);
}
return 0;
}