浅念づ昔夜's Blog

Like author, like book.

0%

CF126B Password

发表于 分类于
本文字数： 476 阅读时长 ≈ 2 分钟

传送门

Solution 1

考虑使用 Z 函数（exkmp）且设 SS 长度为 nn，下标从 00 开始。

设 xx 为保证 i+zi−1<n−1i+z_i-1<n-1 的最大 ziz_i，yy 为保证 i+zi−1=n−1i+z_i-1=n-1 的最大 zi−1z_i-1。那么 max⁡{x,y}\max\{x,y\} 即为在 SS 中间出现的最长 SS 前缀的长度。

设 kk 为保证 i+zi−1=n−1i+z_i-1=n-1 且 zi≤max⁡{x,y}z_i\le \max\{x,y\} 的最大 ziz_i。根据 Z 函数定义，知本题答案为 kk。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int z[N], l, r, minn, maxn;
string str;

void exkmp()
{
    for (int i = 1; i < str.size(); i++) {
        if (i <= r && z[i - l] < r - i + 1)
            z[i] = z[i - l];
        else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < str.size() && str[i + z[i]] == str[z[i]])
                ++z[i];
        }
        if (z[i] > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}

int main()
{
    cin >> str;
    exkmp();
    for (int i = 1; i < str.size(); i++) {
        if (i + z[i] == str.size())
            maxn = max(maxn, z[i]  - 1);
        else if (i + z[i] < str.size())
            maxn = max(maxn, z[i]);
    }
    for (int i = 1; i < str.size(); i++)
        if (i + z[i] == str.size() && z[i] <= maxn)
            minn = max(minn, z[i]);
    if (minn) 
        for (int i = 0; i < minn; i++)
            printf("%c", str[i]);
    else 
        printf("Just a legend");
    return 0;
}

Solution 2

本题也有 KMP 做法。计算出 SS 正序和倒序时的前缀函数 nxtanxta 和 nxtbnxtb。因此只要 SS 正序和倒序时在同一位置有相同长度的相同前后缀，即为满足答案。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int z[N], l, r, nxta[N], nxtb[N], ans;
string str, s;

void kmp()
{
    for (int i = 1; i < str.size(); i++) {
        int j = nxta[i - 1];
        while (j > 0 && str[i] != str[j])
            j = nxta[j - 1];
        if (str[j] == str[i])
            ++j;
        nxta[i] = j;
    }
    s = str;
    for (int i = 0; i < str.size(); i++)
        s[i] = str[str.size() - i - 1];
    for (int i = 1; i < s.size(); i++) {
        int j = nxtb[i - 1];
        while (j > 0 && s[i] != s[j])
            j = nxtb[j - 1];
        if (s[j] == s[i]) 
            ++j;
        nxtb[i] = j;
    }
}

int main()
{
    cin >> str;
    kmp();
    for (int i = 1; i < str.size(); i++) {
        if (nxta[i] == nxtb[str.size() - i - 2 + nxta[i]])
            ans = max(ans, nxta[i]);
    }
    if (ans) 
        for (int i = 0; i < ans; i++)
            printf("%c", str[i]);
    else 
        printf("Just a legend");
    return 0;
}