KMP算法完整代码_kmp算法代码

1.给一个文本串，一个模式串，得出该文本串中第一个与该模式串匹配的初始位置

#include <iostream>
#include <cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>   //有sort函数
using namespace std;

const int MAXM=10000;
const int MAXN=1000000;

int nextTable[MAXM];    //next表
int pattern[MAXN];      //模式串
int text[MAXN];         //文本串

void GetNextTable(int m)   //创建next表
{
    int j=0;
    nextTable[j]=-1;
    int i=nextTable[j];
    while(j<m)
    {
        if(i==-1||pattern[j]==pattern[i]) //这里pattern[j]相当于新串，pattern[i]相当于模式串
        {
            i++;
            j++;
            nextTable[j]=i;    //多了一步更新nextTable表，
        }else{
            i=nextTable[i];
        }
    }
    return ;
}

int KMP(int n,int m)
{
    GetNextTable(m);
    int i=0;
    int j=0;
    while(i<n&&j<m)
    {
        if(j==-1||text[i]==pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j=nextTable[j];
        }
    }
    if(j==m)             //模式串匹配成功
    {
        return i-j+1;     //成功匹配的初始位置
    }
    else{
        return -1;
    }
}

int main()
{
    int caseNumber;
    scanf("%d",&caseNumber);
    while(caseNumber--){
        int n,m;
        scanf("%d%d",&n,&m);        //n为文本串大小，m为模式串大小
        for(int i=0;i<n;++i)
        {
            scanf("%d",&text[i]);   //输入文本串
        }
        for(int j=0;j<m;j++)
        {
            scanf("%d",&pattern[j]);   //输入模式串
        }
        printf("%d\n",KMP(n,m));
    }

}



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

2.给一个文本串，一个模式串，文本串中有多少个子串与模式串完全匹配。

#include <iostream>
#include <cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>   //有sort函数
using namespace std;

const int MAXM=10000;

int nextTable[MAXM];    //next表


void GetNextTable(string pattern)   //创建next表
{
    int m=pattern.size();
    int j=0;
    nextTable[j]=-1;
    int i=nextTable[j];
    while(j<m)
    {
        if(i==-1||pattern[j]==pattern[i]) //这里pattern[j]相当于新串，pattern[i]相当于模式串
        {
            i++;
            j++;
            nextTable[j]=i;    //多了一步更新nextTable表，
        }else{
            i=nextTable[i];
        }
    }
    return ;
}

int KMP(string text,string pattern)
{
    GetNextTable(pattern);
    int n=text.size();
    int m=pattern.size();
    int i=0;
    int j=0;
    int number;     //记录匹配次数
    while(i<n)
    {
        if(j==-1||text[i]==pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j=nextTable[j];
        }
        if(j==m)             //模式串匹配成功
        {
            number++;
            j=nextTable[j];
        }
    }
    return number;

}

int main()
{
    int caseNumber;
    scanf("%d",&caseNumber);
    while(caseNumber--){
        string pattern,text;
        cin>>pattern>>text;
        printf("%d\n",KMP(text,pattern));
    }

}



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