CF126B Password

发表于 | 阅读数

给你一个字符串$S$，找到既是$S$前缀又是$S$后缀又在$S$中间出现过（既不是$S$前缀又不是$S$后缀）的子串

Z函数模版题。

显然我枚举每个前缀的最长公共前缀，记录$T$是否出现过，并且小于$|T|$也要同时标记过。如果此时枚举到后缀，并且出现过一次，则就是答案。

代码 
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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e7 + 10;
int z[N], p[N];
inline void Z(char *s, int n)
{
    for (int i = 1; i <= n; i++)
        z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++)
    {
        if (i <= r)
            z[i] = min(z[i - l + 1], r - i + 1);
        while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}

inline void exkmp(char *s, int n, char *t, int m)
{
    Z(t, m);
    for (int i = 1; i <= n; i++)
        p[i] = 0;
    for (int i = 1, l = 0, r = 0; i <= n; i++)
    {
        if (i <= r)
            p[i] = min(z[i - l + 1], r - i + 1);
        while (i + p[i] <= n && s[i + p[i]] == t[p[i] + 1])
            ++p[i];
        if (i + p[i] - 1 > r)
            l = i, r = i + p[i] - 1;
    }
}
char s[N];
int vis[N];
int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    Z(s, n);
    for (int i = 2; i <= n; i++)
    {
        if (!vis[z[i]])
        {
            while (!vis[z[i]])
                vis[z[i]] = 1, z[i]--;
        }
        else if (z[i] + i - 1 == n)
        {
            for (int j = 1; j <= z[i]; j++)
                printf("%c", s[j]);
            return 0;
        }
    }
    puts("Just a legend");
}