BZOJ 3916 [Baltic2014]friends Hash

题意: 《真·每一年的题只会一题跑系列》 有一个串，把它自己接到了自己后面，然后加了一个字符。 给出加完字符后的串，，询问原串是啥，如果多解输出一坨，无解输出一坨，有唯一解输出串。 解析: sb题。 枚举哪个字符是加的即可。 用上hash之后判断就是o(1)辣 细节什么的自己研究吧。 代码:

;ull;ull hash[N],pow[N];int n;char s[N];ull get_hash(int l,int r){if(l>r)return 0;return hash[r]-hash[l-1]*pow[r-l+1];}int main(){scanf(“%d”,&n);scanf(“%s”,s+1);pow[0]=1;for(int i=1;i<=n;i++)hash[i]=hash[i-1]*base+s[i],pow[i]=pow[i-1]*base;if(!(n&1)){puts(“NOT POSSIBLE”);return 0;}int tmplen=(n-1)>>1;int tmpl,tmpr;int cnt=0;for(int i=1;i<=n;i++){int l1=i-1;int l2=n-i;if(l1<l2){ull hasha=get_hash(1,l1);hasha=hasha*pow[tmplen-l1]+get_hash(i+1,i+tmplen-l1);ull hashb=get_hash(n-tmplen+1,n);if(hasha==hashb){int tmpll=n-tmplen+1,tmprr=n;if(!cnt)tmpl=tmpll,tmpr=tmprr,cnt++;else if(get_hash(tmpl,tmpr)!=get_hash(tmpll,tmprr)){cnt++;break;}}}else if(l1==l2){ull hasha=get_hash(1,tmplen);ull hashb=get_hash(n-tmplen+1,n);if(hasha==hashb){int tmpll=1,tmprr=tmplen;if(!cnt)tmpl=tmpll,tmpr=tmprr,cnt++;else if(get_hash(tmpl,tmpr)!=get_hash(tmpll,tmprr)){cnt++;break;}}}else{ull hasha=get_hash(1,tmplen);ull hashb=get_hash(tmplen+1,l1);hashb=hashb*pow[tmplen-(l1-tmplen)]+get_hash(n-l2+1,n);if(hasha==hashb){int tmpll=1,tmprr=tmplen;if(!cnt)tmpl=tmpll,tmpr=tmprr,cnt++;else if(get_hash(tmpl,tmpr)!=get_hash(tmpll,tmprr)){cnt++;break;}}}}if(cnt>1)puts(“NOT UNIQUE”);else if(cnt==1){for(int i=tmpl;i<=tmpr;i++)printf(“%c”,s[i]);puts(“”);}else puts(“NOT POSSIBLE”);}

靠山山会倒，靠人人会跑，只有自己最可靠。