字符串(1)---KMP & 扩展KMP & Manacher

练习:点击打开链接

字符串也是ACM中的重头戏,基本内容有KMP ,扩展KMP, Manacher ,AC自动机,后缀数组,后缀自动机.按照专题来做共分三部分. LCS LIS LCIS不知道算不算....点击打开链接

小技巧:匹配问题不区分大小写,则将其全部转为小写.

暴力匹配: 用strstr函数就能解决 I M N Z(枚举长度三份)

一.KMP算法

解决单一模式串匹配问题.

利用失配后的nxt数组减少移位,达到O(n)级别.资料自行百度.

延展:

1.求最小循环节点击打开链接就是len-nxt[len] D E(这个题目意思是i为止可以表示成循环的字符) F G

2.求各个循环节 P(先求出最小循环节,然后进入nxtval[i]再求最小循环节累加就是第二小依次循环)

3.字符串最大最小表示法 O(最大最小循环长度就是最小循环节) P(都转为最小 map存放)

4.模式串成功匹配次数(可以有重叠) 匹配成功后j=nxt[j] B

5.模式串成功匹配次数(不能有重叠) 匹配成功后j=0 C

6.既是前缀又是后缀用nextval递归往后 H

7.一个串的最长前缀另一个串的最长后缀,连起来求nxt 完了判断最长的不要大于字符串长就行

8.各种前缀可匹配的次数自左至右计算nxt[]的dp[] ,dp[i]=dp[nxt[i]]+1 ans+=dp[i]

二.扩展KMP

求extand[] 表示以i起始的后缀串与模式串匹配的长度.nxt[] 表示以i起始模式串的后缀串与模式串匹配的长度点击打开链接

1.利用nxt数组求最长后缀串匹配长度裸EXKMP L

三.最长回文

一个串中最长的连续回文.p[i] 以i为中点的最长回文数.点击打开链接

U V W X

其中V是吉哥系列2要求连续规模10^5,有个要求是大于等于,所以加个限制条件就行系列1使用的是LCS,不要求连续规模10^2

不要求连续的回文使用转置再求LCS (HDU1513 点击打开链接)

///核心思想是利用之前已经"匹配"信息减少j移动
///EXKMP方法是记录一个最远匹配位置
///KMP
void getnxt(){
int j = -1;
nxt[0] = -1;
for(int i = 0;i < M;){
if(j == -1 || s2[i] == s2[j]){
i++,j++;
if(s2[i] == s2[j]) nxt[i] = nxt[j];
else nxt[i] = j;
}
else j = nxt[j];
}
}
int KMP(){
getnxt();
int i = 0,j = 0;
while(i < N){   ///这个写错了,不是字符串\0的意思
if(j == -1 || s1[i] == s2[j])
i++,j++;
else j = nxt[j];
if(j==M) return i-M+1;
}
return -1;
}
///EXKMP
void Getnxt(const char *T){
     int len=strlen(T),a=0;
     nxt[0]=len;
     while(a<len-1 && T[a]==T[a+1]) a++;
     nxt[1]=a;
     a=1;
     for(int k=2;k<len;k++){
         int p=a+nxt[a]-1,L=nxt[k-a];
         if( (k-1)+L >= p){
             int j = (p-k+1)>0 ? (p-k+1) : 0;
             while(k+j<len && T[k+j]==T[j]) j++;
             nxt[k]=j;
             a=k;
         }
         else
             nxt[k]=L;
     }
}
void GetExtand(const char *S,const char *T){
     Getnxt(T);
     int slen=strlen(S),tlen=strlen(T),a=0;
     int MinLen = slen < tlen ? slen : tlen;
     while(a<MinLen && S[a]==T[a]) a++;
     extand[0]=a;
     a=0;
     for(int k=1;k<slen;k++){
         int p=a+extand[a]-1, L=nxt[k-a];
         if( (k-1)+L >= p){
             int j= (p-k+1) > 0 ? (p-k+1) : 0;
             while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
             extand[k]=j;
             a=k;
         }
         else
             extand[k]=L;
     }
}

/**
最长回文子串,求的是连续.如果可以不连续则reserve再LCS
http://blog.csdn.net/xingyeyongheng/article/details/9310555
**/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 150000
char fst[maxn];
char sed[2*maxn+2];
int  p[2*maxn+2];
int Manacher(){
    int len = strlen(fst);
    int maxlen =0,id=0;
    for(int i = 0;i < len;i++){
        sed[i*2+1] = '#';
        sed[i*2+2] = fst[i];
    }
    sed[2*len+1] = '#';
    sed[2*len+2] = 0;
    sed[0] = '@';
    len = 2*len+1;
    for(int i = 2;i < len;i++){
        if(p[id] + id > i) p[i] = min(p[2*id-i],p[id]+id-i);
        else p[i] = 1;///公式化简一下 k=i-id  i-k=2id-i
        while(sed[i-p[i]] == sed[i+p[i]]) ++p[i];///害怕这里越界
        if(id+p[id]<i+p[i]) id=i;///i+p[id] 这个写错了....我擦
        maxlen = max(maxlen,p[i]);
    }
    return maxlen-1;
}

int main(){
    while(~scanf("%s",fst))
        printf("%d\n",Manacher());
    return 0;
}

秒客网

字符串(1)---KMP & 扩展KMP & Manacher

相关文章