【P6739 [BalticOI 2014 Day1] Three Friends】题解

题目链接

题目

有一个字符串 \(S\)，对他进行操作：

1. 将 \(S\) 复制为两份，存在字符串 \(T\) 中
2. 在 \(T\) 的某一位置上插入一个字符，得到字符串 \(U\)

现在给定 \(U\)，求 \(S\)。

思路

哈希

先预处理这个字符串的哈希前缀和，然后枚举插入位置，这时候把左右的 \(S\) 求出来，看看是否相同。

需要注意的是，题目是说 \(S\) 不是唯一的猜输出 NOT UNIQUE，也就是说如果有多种切断方式但 \(S\) 一样还是要输出 \(S\)。

总结

这道题是对哈希前缀和的一个非常好的应用。

在哈希里，如果为了防止出错，可以通过求某段区间哈希值，取模等函数的组合，这是以后在做哈希题时可以用到的。

Code

// Problem: P6739 [BalticOI 2014 Day1] Three Friends
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6739
// Memory Limit: 256 MB
// Time Limit: 500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 2000010
//#define M
#define mo 1000000009
int n, m, i, j, k; 
char s[N]; 
int a[N], f[N], mid; 
int l, r; 

int MOD(int x)
{
	return (x%mo+mo)%mo; 
}

int qiu(int l, int r)
{
	if(l>r) return 0; 
	return MOD(a[r]-a[l-1]*f[r-l+1]); 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); scanf("%s", s+1); 
	if(n%2==0) return printf("NOT POSSIBLE"), 0; 
	mid=n/2+1; 
	for(i=f[0]=1; i<=n; ++i)
	{
		f[i]=f[i-1]*29%mo; 
		a[i]=(a[i-1]*29+(s[i]-'A'+1))%mo; 
	}
	for(i=1; i<=n; ++i)
	{
		if(i<=mid)
		{
			r=MOD(qiu(mid+1, n)); 
			l=MOD(qiu(1, i-1)*f[mid-i]+qiu(i+1, mid)); 
		}
		else
		{
			l=MOD(qiu(1, mid-1)); 
			r=MOD(qiu(mid, i-1)*f[n-i]+qiu(i+1, n)); 
		}
		if(l==r)
		{
			if(k && l!=m) return printf("NOT UNIQUE"), 0; 
			k=1; j=i; m=l; 
		}
		// printf("%lld %lld\n", l, r); 
	}
	if(k) 
	{
		if(j