题解：P13790 「CZOI-R6」Border

_ckx_ · 2025-08-21 21:34:44 · 题解

题目大意

给定一个字符串 s，至多修改其中一个字符，使其最长 border 尽量长。

border: 既是前缀又是后缀的子串。

分析

一开始智了，想的是二分，但是机房内阁同学写了一发 WA 了，才发现并没有单调性。

接下来是正解：

由于只能进行一次修改，所以前后缀修改后最多就改变两个位置（两个串有交时改中间）。

所以如果前后缀有 >2 个位置不同，就肯定不能成为 border。

于是可以枚举 border 的长度（也就是答案），找到前后缀的第一个不同字符位置，修改后再判断是否相等（如果有两个位置不同，就判第一和第二个）。

只判第一个和第二个的原因就是上面的结论。

现在问题就是找到第一个不同位置和判相等了，这个直接二分（这下有单调性了） 再加个哈希就行了。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll read()
{
    ll ret = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-' ? -f : f), ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int n;
const int N = 1e6 + 10;
char s[N];
ull h[N] ,pw[N] ,base = 1331;

ull get(int l ,int r) //获取 l ~ r 的子串 hash 值 
{
    if (l > r) return 0;
    return h[r] - h[l - 1] * pw[r - l + 1];
}

int main()
{
    scanf("%s",s + 1); n = strlen(s + 1);

    pw[0] = 1;
    for (int i = 1;i <= n;i++) pw[i] = pw[i - 1] * base;
    for (int i = 1;i <= n;i++) h[i] = h[i - 1] * base + s[i] - 'a'; //hash

    int ans = 0;
    for (int i = 1;i < n;i++)
    {
        int j = n - i + 1;
        int l = 1 ,r = i ,now = 0;
        while (l <= r) //二分找到最后一个相同的位置 
        {
            int mid = l + r >> 1;
            if (get(1 ,mid) == get(j ,j + mid - 1)) now = mid ,l = mid + 1;
            else r = mid - 1;
        }
        if (now == i) //直接匹配上 
        {
            ans = i;
            continue;
        }
        now++; //第一个不同的位置 
        bool f = false;

        //修改前缀的不同字符（第一个不同位置） 
        ull hs = get(1 ,i) - (s[now] - 'a') * pw[i - now]; //hs:前缀扣掉 now位置 的 hash 值 
        for (int c = 0;c < 26;c++) //枚举 now位置 替换成啥 
        {
            ull a = hs + c * pw[i - now] ,b = get(j ,n);

            //可能对后缀也有影响 
            if (j <= now) b += c * pw[n - now] - (s[now] - 'a') * pw[n - now];

            if (a == b) { f = true; break; } //找到可行修改 
        }
        if (f) { ans = i; continue; }

        //同理，修改后缀中的不同字符（第二个不同的位置）
        now = j + now - 1;
        hs = get(j ,n) - (s[now] - 'a') * pw[n - now];
        for (int c = 0;c < 26;c++)
        {
            ull b = hs + c * pw[n - now] ,a = get(1 ,i);
            if (i >= now) a += c * pw[i - now] - (s[now] - 'a') * pw[i - now];
            if (a == b) { f = true; break; }
        }
        if (f) ans = i;
    }

    printf("%d\n",ans);

    return 0;
}