CF126B Password

传送门

Solution 1

考虑使用 Z 函数（exkmp）且设 $S$ 长度为 $n$，下标从 $0$ 开始。

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

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

#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 做法。计算出 $S$ 正序和倒序时的前缀函数 $nxta$ 和 $nxtb$。因此只要 $S$ 正序和倒序时在同一位置有相同长度的相同前后缀，即为满足答案。

#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;
}