【hash】Three friends

【来源】：bzoj3916

【参考博客】

ＢＺＯＪ3916: [Baltic2014]friends

【 哈希和哈希表】Three Friends

【Baltic2014】【BZOJ3916】friends

---

【题解】

首先hash整个串，然后分成三种情况，分别是前半段，中间，后半段，三段的字母试图去掉看能否拼起来。

如果可以，那么还需要考虑是否为唯一的。

唯一的意思是： 串S，如果有选择两个不同的串S也能构成这个原串。

代码还是参考别人写的。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = 2e6+;

 typedef unsigned long long ull ;

 const ull base = ;

 ull Pow[N],Hash[N];

 ull Lstr , Rstr , S;

 char str[N],Ans[N];

 int n,Mid,pos=-;

 // NOT POSSIBLE = Odd or Not found a S

 // NOT UNIQUE = exist least two S

 // Else = The answer S

 // 切割字符串返回hash值

 ull Cut_str( int L ,int R ){

     ull ans = Hash[R] - Hash[L-] * Pow[R-L+] ;

     return ans ;

 }

 bool check (int i){

     //如果未被标记过，则标记 返回true

     //如果标记过，同时这个字符串和暂存的串不一样则返回false

     if( pos == - || S == Lstr ){

         pos = i ;

         S = Lstr ;

         return true ;

     }else{

         return false ;

     }

 }

 int main()

 {

     scanf("%d%s",&n,str+);

     Mid = n >>  ;

     //偶数情况下无法构成

     if( n%== )    return puts("NOT POSSIBLE"),;

     Pow[] = ;

     for(int i=;i<=n;i++){

         Pow[i] = Pow[i-] * base ;

         Hash[i] = Hash[i-] * base + (ull)(str[i]-'A'+);

         //所有字符串只包含大写英文字母

     }

     // delete one character in [1,Mid]

     for(int i= ; i<=Mid ; i++ ){

         Lstr = Cut_str(,i-) * Pow[Mid+-i] + Cut_str(i+,Mid+);

         Rstr = Cut_str(Mid+,n);

         if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),;

     }

     // delete Mid + 1

     Lstr = Hash[Mid] ;

     Rstr = Hash[n] - Hash[Mid+] * Pow[Mid];

     if( Lstr == Rstr ) if( !check(Mid+) ) return puts("NOT UNIQUE"),;

     // delete [Mid+2,n]

     for(int i=Mid+ ; i<=n; i++ ){

         Lstr = Hash[Mid];

         Rstr = Cut_str(Mid+,i-) * Pow[n-i] + Cut_str(i+,n);

         if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),;

     }

     if( pos == - ){

         return puts("NOT POSSIBLE"),;

     }

     int len = n/,cnt =  ;

     for(int i=; i<=n && len ; i++ ){

         if( pos == i ) continue;

         Ans[cnt++] = str[i] ;

         len -- ;

     }

     Ans[cnt] = '\0';

     printf("%s\n",Ans);

     return  ;

 }

 /*

 7

 ABXCABC

 */