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;
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。