字符串的问题（substr，find用法）

链接：https://www.nowcoder.com/acm/contest/77/C
来源：牛客网

字符串的问题

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

有一个字符串让你找到这个字符串 S 里面的子串T 这个子串 T 必须满足即使这个串的前缀也是这个
串的后缀并且在字符串中也出现过一次的(提示要求满足前后缀的同时也要在字符串中出现一次只是前后缀可不行输出最长满足要求字符串)

输入描述:

给出一个字符串 长度 1 到 1e6  全部是小写字母

输出描述:

如果找的到就输出这个子串T 如果不行就输出 Just a legend

示例1

输入

fixprefixsuffix

输出

fix

示例2

输入

abcdabc

输出

Just a legend

ubstr(字符串,截取开始位置,截取长度) //返回截取的字

substr('Hello World',0,1) //返回结果为 'H' *从字符串第一个字符开始截取长度为1的字符串

substr('Hello World',1,1) //返回结果为 'H' *0和1都是表示截取的开始位置为第一个字符

substr('Hello World',2,4) //返回结果为 'ello'

substr('Hello World',-3,3)//返回结果为 'rld' *负数(-i)表示截取的开始位置为字符串右端向左数第i个字符

测试：

select substr('Hello World',-3,3) value from dual;

find函数的使用：

#include<iostream>
#include<cstring>
#include <string>
using namespace std;
string s;
string s1;
int main()
{
    cin >> s;
    cin >> s1;
    cout << s.find(s1) << endl;
}

asdfghhjd

fgh

asd

aaaa

4294967295

本题题解：

 1 #include<iostream>
 2 #include<cstring>
 3 #include <string>
 4 using namespace std;
 5 string s;
 6 int main()
 7 {
 8     cin >> s;
 9     int k = 1, l = s.size();
10     string ans = "";
11     while (l>2 && k<l)
12     {
13         string ss = s.substr(0, k);//拷贝s第0个数开始，长度为k
14         if (s.substr(l - k, k) == ss)
15         {
16             string sss = s.substr(1, l - 2);
17             ///cout << sss.find(ss) << endl;
18             if (sss.find(ss)<l - 2)
19                 ans = ss;
20         }
21         k++;
22     }
23     if (ans == "")
24         cout << "Just a legend" << endl;
25     else
26         cout << ans << endl;
27 }

kmp：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 #define N 1000010
 6 char s[N];
 7 int ne[N],a[N],b[N];
 8 void get(int x)
 9 {
10     ne[0]=ne[1]=0;
11     int i,j;
12     for(i=1;i<x;i++)
13     {
14         j=ne[i];
15         while(j&&s[i]!=s[j])
16             j=ne[j];
17         ne[i+1]=(s[i]==s[j]?j+1:0);
18     }
19 }
20 int main()
21 {
22     int i,j,k,tot;
23     scanf("%s",s);
24     k=strlen(s);
25     get(k);
26     j=k;
27     tot=0;
28     while(ne[j])
29     {
30         if(ne[j])
31             a[tot++]=ne[j];
32         j=ne[j];
33     }
34     for(i=k;i>=0;i--)
35     {
36         b[i]++;
37         b[ne[i]]+=b[i];
38     }
39     for(i=0;i<tot;i++)
40     {
41         if(b[a[i]]>=3)
42         {
43             for(j=0;j<a[i];j++)
44                 printf("%c",s[j]);
45             printf("
");
46             return 0;
47         }
48     }
49     printf("Just a legend
");
50     return 0;
51 }

View Code

我的wa代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 int n,m;
 7 char a[1000005];
 8 char c[1000005];
 9 char b[1000005];
10 int nxt[100007];
11 void get_nxt(int *nxt,char *a,int l)
12 {
13     int i = 0;
14     int j = -1;
15     nxt[0] = -1;
16     while (i < l)
17     {
18         if (j == -1 || a[i] == a[j]) nxt[++i] = ++j;
19         else j = nxt[j];
20     }
21 }
22 bool kmp(char *b,char *a,int la,int lb)
23 {
24     int i, j;
25     i = 0;
26     j = 0;
27     while (i<la)
28     {
29 
30         if (a[i] == b[j] || j == -1) //进行两个字符串的匹配  
31         {
32             i++;//匹配成功，往后继续匹配  
33             j++;
34         }
35         else//匹配完成一次，代表出现了一次，记录下来
36         {
37             j = nxt[j];
38         }
39         if (j == lb)
40         {
41             return 1;
42         }
43     }
44     return 0;
45 }
46 int main()
47 {
48     int k = 1;
49     int i;
50     cin >> a;
51     int n = strlen(a);
52     get_nxt(nxt,a,n);
53     int j=1;
54     bool f = 0;
55     int t = nxt[n];
56     int kk = nxt[n];
57     int p = 0;
58     for (i = 1; i <= n - 1; i++)
59         c[j++] = a[i];
60     while (t)
61     {
62         if (a[kk - p - 1] != a[n - 1]) break;
63         for (j = 0; j <= t - 1; j++)
64             b[j] = a[j];
65         j = 1;
66         m = t;
67         memset(nxt, 0, sizeof(nxt));
68         get_nxt(nxt, b, t);
69         f = kmp(b, c, n - 2 * t, t);
70         if (f)
71         {
72             for (j = 0; j <= t - 1; j++)
73                 cout << b[j];
74             break;
75         }
76         t--;
77         p++;
78     }
79     if (!f) cout << "Just a legend" << endl;
80     else cout << endl;
81     return 0;
82 }

View Code