BZOJ 3916 friend文字列hash

タイトルの説明
3人の親友が一緒にゲームをするのが好きで、A君は次の文字列Sを書いて、B君はそれをコピーしてTを得て、C君はTの任意の位置(首尾を含む)に1つの文字を挿入してUを得て、今あなたはUを得て、Sを見つけてください.
入力
1行目の数Nは、Uの長いを表す.
2行目の文字列Uは、Uが大文字で構成されていることを保証します.
しゅつりょく
1行出力、Sが存在しなければ「NOT POSIBLE」を出力.Sが一意でない場合は「NOT UNIQUE」を出力.そうでなければ出力S.
サンプル入力
Sample Input1: 7 ABXCABC Sample Input2: 6 ABCDEF Sample Input3: 9 ABABABABA
サンプル出力
Sample Output1: ABC Sample Output2: NOT POSSIBLE Sample Output3: NOT UNIQUE
问题解:まず性质を见つけて、偶数の长さの一定は存在しないで、直接出力します.奇数の長さについては、そっくりの列が連なっているのでhashを直接思いつき、hash値が等しければ同じ列となり、どこに文字が挿入されているのか分からないので位置を列挙し、位置が変化しているため、対応する分割された2つの列も異なるので、先に列の接頭辞を処理し、直接加算して減算すればよい.この問題のもう一つの性質は,挿入位置が前半の場合,(n/2+1~~n)は必ず最初の列であり,挿入位置が後半の場合,(1~~n/2)は必ず最初の列である.
まとめ:hashは文字列を処理する有力なツールであり、hash値は通常大きいのでunsigned long longで格納することに注意してください.どんなテーマを手に入れても、まず10分で法則や性質があるかどうかを考えて、往々にして法則、性質を見つけて相応のアルゴリズムを付き合うことができます.

#include 
#include 
#include 
#include 
#define N 2000010
using namespace std;
int n,Hash[N],tmp[N],ans,flag=0,opt;
char str[N];
int main()
{
	scanf("%d%s",&n,str+1);
	if(!(n%2))
	{
		printf("NOT POSSIBLE
");
		return 0;
	}
	tmp[0]=1;
	for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*131+str[i],tmp[i]=tmp[i-1]*131;
	unsigned long long x,y;
	for(int i=1;i<=n;i++)
	{
		if(i<=n/2) x=Hash[n/2+1]-Hash[i]*tmp[n/2+1-i]+Hash[i-1]*tmp[n/2-i+1];
		else x=Hash[n/2];
		if(i<=n/2+1) y=Hash[n]-Hash[n/2+1]*tmp[n/2];
		else y=Hash[n]-Hash[i]*tmp[n-i]+(Hash[i-1]-Hash[n/2]*tmp[i-1-n/2])*tmp[n-i];
		if(x==y)
		{
			if(flag && ans!=x)
			{
				printf("NOT UNIQUE
");
				return 0;
			}
			flag=1;ans=x;opt=i;
		}
	}
	if(!flag)
    {
        printf("NOT POSSIBLE
");
        return 0;
    }
	int cnt=1;
	for(int i=1;cnt<=n/2;i++)
	    if(i!=opt)
	       cout<