kmp&exkmp

发表于 | 更新于: | 分类于 | | 阅读数

之前写过kmp的算法，lwl给了我一个模板，现在再写就出问题了，出来挨打！，不过还好发现的及时。

KMP

Extend to Palindrome

题意：就是在一个字符串最后添加最少的字符，使得字符串回文。

思路：求一个正序的串，和一个逆序的串，求其中的正向的后缀和逆向的前缀相等的长度最大值，最后先输出正向的串，在输出逆序中最大长度之后的字符。

比如说 正序：abaa，逆序：aaba ，那么最长的长度就是2，为aa，然后就输出abaa ba就好了，可以kmp或者hash求最长的长度。

KMP法（模板拿稳了）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1e5+10;
char s[maxn];
char t[maxn];
int nex[maxn],len;
void cal(){
    int i,j;
    nex[0]=j=-1;
    i=0;
    while(i<len){
        while(j!=-1 && s[j]!=s[i]) j=nex[j];
        nex[++i]=++j;
    }
}
int kmp(){
    int i=0,j=0;
    //原串t，目的串s
    while(i<len&&j<len){
        while(j!=-1 && t[i]!=s[j]) j=nex[j];
        i++;
        j++;
    }
    return j;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%s",t)){
        len=strlen(t);
        for(int i=0; i<len; i++){
            s[i]=t[len-i-1];
        }
        s[len]='\0';
        cal();
        printf("%s",t);
        int tt=kmp();
        for(int i=tt; i<len; i++) putchar(s[i]);
        puts("");
    }
}

hash留坑吧……

后记：如果是求在任意位置插入任意字符，求插入的最少字符的个数，做法就是区间dp。

扩展KMP

用kmp硬刚扩展kmp算法，我哭了。😭

HDU6629

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
char s[maxn];
char t[maxn];
ll nex[maxn],len;
void cal(){
    memset(nex,0,sizeof nex);
    int i,j;
    nex[0]=j=-1;
    i=0;
    while(i<len){
        while(s[j]!=s[i] && j!=-1) j=nex[j];
        nex[++i]=++j;
    }
}
ll Next[maxn];
void getNext(char t[],ll m){
    Next[0]=m;
    ll j=0;
    while(j+1<m&&t[j]==t[j+1]) j++;
    Next[1]=j;
    ll k=1;
    for(ll i=2;i<m;i++){
        ll p=Next[k]+k-1;
        ll L=Next[i-k];
        if(i+L<p+1) Next[i]=L;
        else {
            j=max(0LL,p-i+1);
            while(i+j<m&&t[i+j]==t[j]) j++;
            Next[i]=j;
            k=i;
        }
    }
}
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%s",s);
        len=strlen(s);
        cal();
        getNext(s,len);
        ll ans=0;
        for(ll i=1; i<len; i++){
            //printf("%d\n",Next[i]);
            ans+=(Next[i]);
            if(Next[i]+i>=len)ans+=0;
            else ans++; 
        }
        printf("%lld\n",ans);
    }
}

模板

（感谢清巨orz）

1.KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//next[i] 表示t[i-next[i]...i-1]=t[0...next[i]-1]
//循环节len=m%(m-next[m])==0?m-next[m]:1
void getNext(char t[],int m){
    int i,j;
    j=Next[0]=-1;
    i=0;
    while(i<m){
        while(j!=-1&&t[i]!=t[j]) j=Next[j];
        Next[++i]=++j;
        //if(t[++i]==t[++j]) Next[i]=Next[j]; //优化
        //else Next[i]=j;
    }
}
int kmp(char s[],int n,char t[],int m){
    getNext(t,m);
    int i=0,j=0;
    while(i<n){
        while(j==-1&&s[i]!=t[j]) j=next[j];
        i++,j++;
        if(j>=m){	//匹配成功
            ;
        }
    }
}

2.扩展KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//next[i]表示t[i...m-1]与t[0...m-1]的最长公共前缀
//extend[i]表示s[i...n-1]与t[0...m-1]的最长公共前缀
int Next[maxn],extend[maxn];
void getNext(char t[],int m){
    Next[0]=m;
    int j=0;
    while(j+1<m&&t[j]==t[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<p+1) Next[i]=L;
        else {
            j=max(0,p-i+1);
            while(i+j<m&&t[i+j]==t[j]) j++;
            Next[i]=j;
            k=i;
        }
    }
}

void extendkmp(char t[],int m,char s[],int n){
    getNext(t,m);
    int j=0;
    while(j<n&&j<m&&t[j]==s[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<p+1) extend[i]=L;
        else {
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&s[i+j]==t[j]) j++;
            extend[i]=j;
            k=i;
        }
    }
}
thanks!