题解：P13790 「CZOI-R6」Border

题目大意

给定一个字符串

s

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

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

分析

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

接下来是正解：

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

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

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

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

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

code

CPP

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

题解：P13790 「CZOI-R6」Border

文章操作

题目大意

分析

接下来是正解：

code

相关推荐

评论

题解：P13790 「CZOI-R6」Border