中国制造网国际站,wordpress 文章图片插件,网站建设代理网站,写作网站投稿赚钱链接 next数组的巧妙应用 学弟出给学弟的学弟的题。。 求最长的 是前缀也是后缀同时也是中缀的串 next的数组求的就是最长的前后缀 但是却不能求得中缀 所以这里 就把尾部去掉之后再求 这样就可以保证是中缀了 先把所有既是前缀也是后缀的长度的求出来标记 然后再去掉尾部 求…链接 next数组的巧妙应用 学弟出给学弟的学弟的题。。 求最长的 是前缀也是后缀同时也是中缀的串 next的数组求的就是最长的前后缀 但是却不能求得中缀 所以这里 就把尾部去掉之后再求 这样就可以保证是中缀了 先把所有既是前缀也是后缀的长度的求出来标记 然后再去掉尾部 求一下最大 既是前缀又是后缀的长度 1 #include iostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includestdlib.h6 #includevector7 #includequeue8 #includevector9 using namespace std;
10 #define INF 0xfffffff
11 #define N 1000010
12 char s[N];
13 int next[N];
14 int vis[N];
15 void kmp(int k)
16 {
17 int i,j-1;
18 next[0] -1;
19 for(i 1 ; i k ; i)
20 {
21 while(j-1s[i]!s[j1])
22 j next[j];
23 if(s[i]s[j1])
24 j;
25 next[i] j;
26 }
27 }
28 int main()
29 {
30 //freopen(data.in,r,stdin);
31 //freopen(data1.out,w,stdout);
32 int n,i;
33 int kk1;
34 cinn;
35 while(n--)
36 {
37 memset(vis,0,sizeof(vis));
38 memset(next,0,sizeof(next));
39 cins;
40 int k strlen(s);
41 kmp(k);
42 int len next[k-1];
43 vis[len] 1;
44 while(len!-1)
45 {
46 vis[next[len]] 1;
47 len next[len];
48 }
49 int mm 0;
50 for(i 0 ; i k-1 ; i)
51 if(vis[next[i]]) mm max(mm,next[i]1);
52 if(mm)
53 {
54 for(i 0 ;i mm ; i)
55 couts[i];
56 puts();
57 }
58 else
59 puts(Bad Luck!);
60 }
61 return 0;
62 }
63
64 /**************************************
65 Problem id : SDUT OJ 2784
66 User name : shang
67 Result : Accepted
68 Take Memory : 9240K
69 Take Time : 180MS
70 Submit Time : 2014-02-15 15:57:03
71 **************************************/ View Code 转载于:https://www.cnblogs.com/shangyu/p/3550620.html
