当前位置：网站首页>YTU 2297: KMP pattern matching three (string)

YTU 2297: KMP pattern matching three (string)

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

题目描述

输入一个主串和一个子串,若匹配成功,Then find the number of matches and the position of the substring in the main string,若匹配不成功,则输出0

输入

输入两个字符串

输出

Output matching pass number and position

样例输入

       
       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])     
       
       //The main string matches the corresponding characters of the pattern string successfully
       
        {
       
       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.