KMP模式匹配

题目描述

输入一个主串和一个子串,若匹配成功,则找出匹配的趟数和在子串在主串中的位置,若匹配不成功,则输出0

输入要求

输入两个字符串

输出要求

输出匹配的趟数和位置

假如输入

ababcabcacbab
abcac

应当输出

3 6

Code:

今天好好地理解了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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
void getnext(char str[],int next[])
{
    int i=0,j=-1;
    next[0]=-1;
    int len=strlen(str);
    while(i<len-1)
    {
        if(j==-1||str[i]==str[j])
        {
            ++i;
            ++j;            
            next[i]=j;
        }
        else
            j=next[j];
    }
}
void kmp(char str[],char substr[],int next[],int &times,int &pos)
{
    int len1=strlen(str);
    int len2=strlen(substr);
    int i=0,j=0;
    times=1;
    getnext(substr,next);
    while(i<len1&&j<len2)
    {
        if(j==-1||str[i]==substr[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];        
            ++times;
        }
    }
    if(len2==j)
        pos=i-j;
    else
        times=0;
}
int main()
{
    char str[100],substr[100];
    gets(str);
    gets(substr);
    int next[100];
    int pos,times;
    kmp(str,substr,next,times,pos);
    if(times)
        cout<<times<<" "<<pos+1;
    else
        cout<<0;
    return 0;
}

打个小广告

欢迎加入我的知识星球「基你太美」,我会在星球中分享 AucFrame 框架、大厂面经、AndroidUtilCode 更详尽的说明…一切我所了解的知识,你可以通过支付进入我的星球「基你太美」进行体验,加入后优先观看星球中精华的部分,如果觉得星球的内容对自身没有收益,你可以自行申请退款退出星球,也没必要加我好友;如果你已确定要留在我的星球,可以通过扫描如下二维码(备注:基你太美+你的星球昵称)加我个人微信,方便我后续拉你进群(PS:进得越早价格越便宜)。

我的二维码