当前位置：网站首页>YTU 2297: KMP模式匹配三（串）

YTU 2297: KMP模式匹配三（串）

2022-08-11 08:35:00 【51CTO】

题目描述

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

输入

输入两个字符串

输出

输出匹配的趟数和位置

样例输入

       
       ababcabcacbab
       
abcac
      
1.
2.

样例输出

迷失在幽谷中的鸟儿，独自飞翔在这偌大的天地间，却不知自己该飞往何方…

       
       #include <stdio.h>
       
       #include <string.h>
       
       #define SizeMax 105
       
       typedef 
       
       struct
       
{
       
       char 
       
       data[
       
       SizeMax];
       
       int 
       
       length;
       
} 
       
       SqString;
       
       void 
       
       getnext(
       
       SqString 
       
       s,
       
       int 
       
       next[])
       
{
       
       int 
       
       j
       
       =
       
       0,
       
       k
       
       =-
       
       1;
       
       next[
       
       0]
       
       =-
       
       1;
       
       while(
       
       j
       
       <
       
       s.
       
       length
       
       -
       
       1)
       
    {
       
       if(
       
       k
       
       ==-
       
       1
       
       ||
       
       s.
       
       data[
       
       j]
       
       ==
       
       s.
       
       data[
       
       k])
       
       j
       
       ++,
       
       k
       
       ++,
       
       next[
       
       j]
       
       =
       
       k;
       
       else 
       
       k
       
       =
       
       next[
       
       k];
       
    }
       
}
       
       void 
       
       StrAssign(
       
       SqString 
       
       &
       
       s,
       
       char 
       
       cstr[])
       
{
       
       int 
       
       i;
       
       for(
       
       i
       
       =
       
       0; 
       
       i
       
       <(
       
       int)
       
       strlen(
       
       cstr); 
       
       i
       
       ++)
       
       s.
       
       data[
       
       i]
       
       =
       
       cstr[
       
       i];
       
       s.
       
       length
       
       =
       
       i;
       
}
       
       int 
       
       kmp(
       
       SqString 
       
       s,
       
       SqString 
       
       t,
       
       int 
       
       next[],
       
       int 
       
       &
       
       ci)
       
{
       
       int 
       
       i
       
       =
       
       0,
       
       j
       
       =
       
       0;
       
       while(
       
       i
       
       <
       
       s.
       
       length
       
       &&
       
       j
       
       <
       
       t.
       
       length)
       
    {
       
       if(
       
       j
       
       ==-
       
       1
       
       ||
       
       s.
       
       data[
       
       i]
       
       ==
       
       t.
       
       data[
       
       j])     
       
       //主串与模式串对应字符匹配成功
       
        {
       
       i
       
       ++;
       
       j
       
       ++;
       
        }
       
       else 
       
       j
       
       =
       
       next[
       
       j],
       
       ci
       
       ++;                
       
       //模式串指针回溯
       
    }
       
       if(
       
       j
       
       >=
       
       t.
       
       length)
       
       return 
       
       i
       
       -
       
       t.
       
       length
       
       +
       
       1;
       
       else 
       
       return 
       
       0;
       
}
       
       int 
       
       main()
       
{
       
       SqString 
       
       s,
       
       t;
       
       int 
       
       next[
       
       SizeMax]
       
       = {
       
       -
       
       1},
       
       ci
       
       =
       
       1;
       
       char 
       
       c[
       
       SizeMax],
       
       d[
       
       SizeMax];
       
       gets(
       
       c);
       
       gets(
       
       d);
       
       StrAssign(
       
       s,
       
       c);                 
       
       //建立串
       
       StrAssign(
       
       t,
       
       d);
       
       getnext(
       
       t,
       
       next);                
       
       //得到next值
       
       int 
       
       k
       
       =
       
       kmp(
       
       s,
       
       t,
       
       next,
       
       ci);         
       
       //solve
       
       printf(
       
       "%d %d\n",
       
       ci,
       
       k);
       
       return 
       
       0;
       
}
       
       /*
       
       acabaabaabcacaabc
       
       abaabcac
       
       4 6
       
       */
      
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.