10
25
2015
0

KMP+Manacher学习笔记

KMP是一种可以在最坏O(n+m)的时间内完成匹配的字符串匹配算法。学了这个也有一些时间了,也是时候写一点学习笔记了。

KMP需要处理一个next数组,也就是当匹配失败后应该跳转到的匹配位置。

算法如下(懒癌晚期,简直啥也没说)

UPD:代码里面有一个明显的错误今天才发现……我水平怎么这么低……为被坑到的同学们道个歉……555 ——2016.6.21

char a[1000005],b[105];
int next[105];
//a表示需要匹配的串,b表示模式串

void Fill() {
next[1]=0;
int n=strlen(a+1);
for(int i=2,j=0;i<=n;i++) {
    while(j>0&&a[i]!=a[j+1])j=next[j];
    if(a[i]==a[j+1])j++;
    next[i]=j;
}
}

//以下Find函数的mode意思是:当mode=0时,输出匹配成功的位置;mode=1时,输出出现的次数.

int Find(int mode){
Fill();
int ans=0;
int n=strlen(a+1),m=strlen(b+1);
for(int i=1,j=0;i<=m;i++) {
    while(j>0&&(j==n||b[i]!=a[j+1]))j=next[j];
    if(b[i]==a[j+1])j++;
    if(j==n)ans++;
}
return ans;
}

接下来是Manacher算法。

这是一种可以O(n)解决回文子串的算法。详见这里

你萌不觉得我的代码简直就是背模版么233

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int p[240005],len;
char s[240005];

int main(){
freopen("3068.in","r",stdin);
freopen("3068.out","w",stdout);
while(scanf("%s",s)!=EOF){
    int len=strlen(s),id=0,maxlen=0;
    for(int i=len;i>=0;i--){
        s[i*2+1]='#';
        s[i*2+2]=s[i];
    }
    s[0]='*';
    s[len*2+3]='\0';
    for(int i=2;i<2*len+1;i++){
        if(p[id]+id>i){
            p[i]=min(p[id*2-i],p[id]+id-i);
        }
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(id+p[id]<i+p[i])id=i;
        if(p[i]>maxlen)maxlen=p[i];
    }
    printf("%d\n",maxlen-1);
}
return 0;
}
Category: OI | Tags: OI | Read Count: 638

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com