当前位置：网站首页>YTU 2295: KMP pattern match one (string)

YTU 2295: KMP pattern match one (string)

2022-08-10 13:19:00 【51CTO】

2295: KMP模式匹配一（串）

时间限制: 1 Sec 内存限制: 128 MB

提交: 32

解决: 22

题目描述

求子串的next值,用next数组存放,全部输出

输入

输入一个字符串

输出

输出所有next值

样例输入

       
       abaabcac
      
1.

样例输出

       
       0 1 1 2 2 3 1 2
      
1.

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

       
       #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 
       
       main() 
       
{ 
       
       SqString 
       
       s; 
       
       int 
       
       next[
       
       SizeMax]
       
       ={
       
       -
       
       1}; 
       
       char 
       
       c[
       
       SizeMax]; 
       
       gets(
       
       c); 
       
       StrAssign(
       
       s,
       
       c);         
       
       //建立串s
       
       getnext(
       
       s,
       
       next);        
       
       //得到next值
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       s.
       
       length;
       
       i
       
       ++) 
       
       printf(
       
       i
       
       !=
       
       s.
       
       length
       
       -
       
       1
       
       ?
       
       "%d ":
       
       "%d\n",
       
       next[
       
       i]
       
       +
       
       1); 
       
       return 
       
       0; 
       
}
      
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.