KMP算法

发表于
字数统计: 297 | 阅读时长 ≈ 1

先存代码以后填坑

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;


void getNEXT(const string &s,int *NEXT) //改进后
{
    NEXT[0] = -1;
    int j = 0,k = -1;
    while(j < s.size()-1)
    {

        if (k == -1 || s[j] == s[k])
        {

            if  (s[++j] == s[++k])
                NEXT[j] = NEXT[k];
            else
                NEXT[j] = k;
        }
        else
            k = NEXT[k];
    }
}

void getnext(const string &s,int *next) //未改进
{
    next[0] = -1;
    int j = 0,k = -1;
    while (j < s.size()-1)
    {
        if (k == -1 || s[j] == s[k])
            next[++j]=++k;
        else
            k = next[k];
    }
}




int KMP(string &ob,string &pat)  //返回第一次匹配成功的角标
{
    int obsize=ob.size();
    int patsize=pat.size();
    int *next=new int[patsize];
    getnext(pat,next);
    int i=0,j=0;
    while(i<obsize&&j<patsize&&obsize-i>=patsize-j)
    {
        if(j==-1 || ob[i]==pat[j])
        {i++;j++;}
        else
        {j=next[j];}
    }
    delete []next;
    if(j==patsize)
    return i-j;
    else
    return -1;
}
int main()
{
    while(true){
    string s;
    cin >> s;
    int *NEXT=new int[s.size()];
    int *next=new int[s.size()];
    getNEXT(s,NEXT);
    getnext(s,next);
    for(int i=0;i<s.size();i++)
    cout<<next[i]<<' ';
    cout<<endl;
    for(int i=0;i<s.size();i++)
    cout<<NEXT[i]<<' ';
    cout<<endl;
    string ss;
    cin>>ss;
    cout<<KMP(ss,s)<<endl;
    }
    system("pause");
    return 0;
}



//abcaabbabcabaacbacba