F-Palindrome hash+枚举

扫了一眼数据，长度和小于1e4，很快啊，一个暴力代码出来了。
梦幻云端彩虹桥上的zcs仙女说过：“Think twice, code once. And debug for the rest of your life.”
由于对hash的理解不透彻，直到赛后才过了这题(痛哭)。

思路：

从最朴素的枚举算法入手，枚举两个位置的复杂度为O(n) ,那么就必须做到在O(1) 的复杂度内判断是否能构成回文串。而判断回文可以也使用 通过判断字符串正序逆序是否相等 的途径，于是自然而然就想到了O(1)判断字符串是否相等的哈希算法。

但与简单的hash不同的是，此题中需要处理两个删除字符的操作，这两个被删除的位置将整个串拆成了前中后三个子串，如图：

回想hash公式：

由于前缀原理，我们可以把 “hash数组的构造” 与 “求部分子串的hash值” 看作一个正解与反解的相逆过程。我们可以通过每个字符的s[i]不断累加正向的构造hash数组，也可以通过不同位之间由p的次方构造的关系求得子串的hash值。
那么在已知三个子串hash值的情况下，只需要通过乘p的次方就可以拼接出完整回文串的hash值。

上述思路可能过与抽象，下面附上这部分的代码和注释，可能会帮您更好的理解：

//拼接计算
ull GetHash(int p1,int p2){    //p1,p2即为删除位，将s分割成t1,t2,t3三个子串
     ull t1=Hash[p1-1];    //t1为[1,p1)的部分
     ull t2=Hash[p2-1]-Hash[p1]*bin[p2-1-p1];            //t2为(p1,p2)的部分
     ull t3=HashR[n]-Hash[p2]*(bin[n-p2]);               //t3为(p2, n]的部分

     return t1*bin[(p2-p1-1)+(n-p2)]+t2*bin[(n-p2)]+t3;
       //t1需要乘以 p 的 (len t2 + len t3)次方，t2需要乘以 p 的 (len t2)次方
}

完整代码：

#include<bits/stdc++.h>
using namespace std;

const int P=13;

int n,t;
char s[20005];
unsigned long long hashP[2005],hashR[2005];

unsigned long long bin[2005];

void makeBin(){
     bin[0]=1;
     for(int i=1;i<=2000;i++){
          bin[i]=bin[i-1]*P;
     }
     return ;
}

void makeHash(){
     for(int i=1;i<=n;i++) hashP[i]=hashP[i-1]*P+s[i]-'a';
     for(int i=n;i>=1;i--) hashR[n+1-i]=hashR[n-i]*P+s[i]-'a';
}

unsigned long long GetHashP(int p1,int p2){
     unsigned long long t1=hashP[p1-1];
     unsigned long long t2=hashP[p2-1]-hashP[p1]*bin[p2-1-p1];
     unsigned long long t3=hashP[n]-hashP[p2]*(bin[n-p2]);

     return t1*bin[(p2-p1-1)+(n-p2)]+t2*bin[(n-p2)]+t3;
}

unsigned long long GetHashR(int p1,int p2){
     unsigned long long t1=hashR[p1-1];
     unsigned long long t2=hashR[p2-1]-hashR[p1]*bin[p2-1-p1];
     unsigned long long t3=hashR[n]-hashR[p2]*(bin[n-p2]);

     return t1*bin[(p2-p1-1)+(n-p2)]+t2*bin[(n-p2)]+t3;
}


int main()
{
     makeBin();
     scanf("%d",&t);
     while(t--){
          cin>>n>>s+1;
          makeHash();
          bool flag=false;
         for(int i=1;i<=n;i++){
              for(int j=i+1;j<=n;j++){
                   unsigned long long left=GetHashP(i,j);
                   unsigned long long right=GetHashR(n+1-j,n+1-i);
                   if(left==right) flag=true;
                   if(flag) break;
             }
             if(flag) break;
         }
         if(flag) printf("Yes\n");
         else printf("No\n");
     }

     return 0;
}