目录
KMP模式匹配算法
Manacher最长回文子串算法
给出长度n的主串和长度m的模式串进行模式匹配,复杂度O(n+m)
预处理出失败指针(最长公共前后缀),进行平摊为O(1)的转移
int nxt[maxn]; void build_next(char *s){ int len = strlen(s+1); for(int i=2,j=0;i<=len;i++){ // j为之前已匹配成功的长度 while(j && s[i]!=s[j+1]){ j = nxt[j]; } if(s[j+1]==s[i]){ j++; } nxt[i] = j; } } void Kmp(char *T,char *P){ build_next(P); int la = strlen(T+1); int lb = strlen(P+1); for(int i=1,j=0;i<=la;i++){ // j为之前已匹配成功的长度 while(j&&T[i]!=P[j+1]){ // 通过失败指针找到可以成功的位置或找不到 j = nxt[j]; } if(T[i]==P[j+1]){ // 匹配成功 匹配成功长度+1 j ++; } if(j==lb){ printf("%d\n",i-lb+1); j = nxt[j]; } } }给定长度为n的字符串,O(n)的复杂度找到其最长回文子串的长度
利用之前已找出的回文串的长度,先确定一部分的回文串长度,然后在这个基础上延伸
char s[maxn],str[maxn]; int n,len[maxn]; // 以i为中心的最长回文串的半径 void init(){ str[0] = str[1] = '#'; // 将字符串预处理出来 for(int i=0;i<n;i++){ str[2*i+2] = s[i]; str[2*i+3] = '#'; } n = n*2 + 2; str[n] = 0; } int Manacher(){ init(); int mx=0,id=0,ans=0; for(int i=1;i<n;i++){ if(i<mx){ len[i] = min(len[2*id-i],mx-i); //该点的半径在对称点的基础上延伸 }else{ len[i] = 1; } for(;str[i-len[i]] == str[i+len[i]];len[i]++); if(i+len[i] > mx){ // 记录之前找到的最长回文子串的延伸的最右边和中心点 mx = i+len[i]; id = i; } ans = max(ans,len[i]); } return ans - 1; }
