【2018年全国多校算法寒假训练营练习比赛(第五场)-C】字符串问题(KMP)

题目链接:https://www.nowcoder.com/acm/contest/77/C

【题意】

求一个字符串中最长的子串,要求子串既是原串的前缀又是后缀,除前后缀还在中间出现过。

【思路】

KMP的应用,首先要理解next数组的含义:一个字符串中 前缀 和 后缀的最长公共长度,next的值也是在匹配原串时如果不匹配时返回的下标值,而不是从头匹配。

本题要满足中间也出现,也就是说next[j] = next[i](j < i)。但是最长的不一定在中间出现过,也可能是最长的一部分,比如1112113111.

解决这个问题只需要让j = next[j-1]就好了。

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6+5;
 4 char s[N];
 5 int Next[N], num[N];
 6 void make_Next(int n)
 7 {
 8     int i,j;
 9     for(i=1,j=0; i<n; i++)
10     {
11         while(j>0&&s[i]!=s[j])
12             j=Next[j-1];
13         if(s[i]==s[j])
14             j++;
15         Next[i]=j;
16     }
17 }
18 int main()
19 {
20     scanf("%s",s);
21     int len=strlen(s);
22     Next[0]=0;
23     make_Next(len);
24     int n = Next[len-1];
25     bool f = 0;
26     for(int i = 1; i < len-1; i++)
27         num[Next[i]]++;//标记数组
28     while(n)
29     {
30         if(num[n])
31         {
32             f = 1;
33             break;
34         }
35         n = Next[n-1];
36     }
37     if(f == 0) puts("Just a legend");
38     else
39     {
40         for(int i = 0; i < n; i++)
41             printf("%c", s[i]);
42         cout<<endl;
43     }
44     return 0;
45 }

相关推荐