题解 P3893 【[GDOI2014]Beyond】

Jayun · 2021-05-12 13:50:57 · 题解

链接：

洛谷

博客园

题目大意:

在一个圆环上从两个位置出发转圈圈，经过的位置随机变换，求环的最大长度。

正文：

假设我们以及知道了环的最大长度 l。由于这是一个环，所以 A 串的部分一和 B 串的部分二、A 串的部分二和 B 串的部分一必定相同：

一个串的第一部分在另一个串里找相同的第二部分的这个过程，就可以用扩展 KMP 实现。也就是两次扩展 KMP 的得到 A 对于 B 的 z 函数 z_1(i)，和 B 对于 A 的 z 函数 z_2(i)。现在考虑怎么通过这两个 z 函数求出答案。

设对于 A 串，第一部分结尾在 i 处；对于 B 串，第二部分结尾在 j 处。很容易得到 i+j=l，且 z_1(i+1)\geq j,z_2(j+1)\geq i。

由于对于每一个 i 可以通过 z_1(i+1) 得到 j 的上界，于是可以通过树状数组维护 j，同时对于每一个 i 也可以求出最大的合法的 j。

const int N = 4e6 + 10;

inline ll READ()
{
    ll x = 0, f = 1;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') f = -f, c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}

int n;
string a, b;
int z1[N], z2[N];

void exKMP(string s, int *z)
{
    int len = s.size(), l = 0;
    for (int i = 1; i < len; i++)
    {
        if (l + z[l] > i) z[i] = min(z[l] - i + l, z[i - l]);
        while (i + z[i] < len && s[z[i]] == s[z[i] + i]) z[i]++;
        if (i + z[i] > l + z[l]) l = i;
    }
}

vector <int> vec[N];
ll ans;
ll t[N];

void modify(int x)
{
    for (int i = x; i <= n; i += i & -i) t[i] = max(t[i], 1ll * x);
}
ll query(int x)
{
    ll ans = 0;
    for (int i = x; i; i -= i & -i) ans = max(t[i], ans);
    return ans;
}

int main()
{
    n = READ();
    cin >> a; cin >> b;
    exKMP(a + b, z1);
    exKMP(b + a, z2);
    for (int i = 1; i <= n; i++)            // 这里 z1[i]、z2[i] 的下标还是从一开始的
        z1[i] = z1[i + n - 1], z1[i + n - 1] = 0,
        z2[i] = z2[i + n - 1], z2[i + n - 1] = 0;
    for (int j = 1; j < n; j++)
        vec[z2[j + 1]].push_back(j);
    for (int i = n - 1; i; i--) 
    {
        for (int j : vec[i])
            modify(j);
        ll j = query(z1[i + 1]);
        if (j) ans = max(ans, i + j);
    }
    printf ("%lld\n", ans);
    return 0;
}