CF 2010 C2. Message Transmission Error (hard version) (*1700) 字符串+哈希

CF 2010 C2. Message Transmission Error (hard version) (*1700) 字符串+哈希

题目链接

题意：

给你一个字符串，让你判断是否是由某个字符串首尾拼接重叠而成的。

思路：

做法很多，最暴力就直接枚举字符串长度，然后哈希即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

struct Hash{
   const int mod1=100663319,mod2=201326611;
   const LL P1=131,P2=13331;
   vector<LL> p1,p2,h1,h2,t1,t2;

   void init(string s){
      int n=(int)s.size()-1;
      p1.assign(n+1,0);p2.assign(n+1,0);
      h1.assign(n+1,0);h2.assign(n+1,0);
      t1.assign(n+2,0);t2.assign(n+2,0);
      p1[0]=p2[0]=1;
      for(int i=1;i<=n;i++){
         p1[i]=p1[i-1]*P1%mod1;
         p2[i]=p2[i-1]*P2%mod2;
         h1[i]=(h1[i-1]*P1%mod1+s[i]-'0'+1)%mod1;
         h2[i]=(h2[i-1]*P2%mod2+s[i]-'0'+1)%mod2;
      }
      for(int i=n;i>=1;i--){
         t1[i]=(t1[i+1]*P1%mod1+s[i]-'0'+1)%mod1;
         t2[i]=(t2[i+1]*P2%mod2+s[i]-'0'+1)%mod2;
      }
   }

   int getHash1(int l,int r){
      return (h1[r]-(h1[l-1]*p1[r-l+1])%mod1+mod1)%mod1;
   }

   int getHash2(int l,int r){
      return (h2[r]-(h2[l-1]*p2[r-l+1])%mod2+mod2)%mod2;
   }

   int getRevHash1(int l,int r){
      return (t1[l]-(t1[r+1]*p1[r-l+1])%mod1+mod1)%mod1;
   }

   int getRevHash2(int l,int r){
      return (t2[l]-(t2[r+1]*p2[r-l+1])%mod2+mod2)%mod2;
   }
}Hash;
void Showball(){
   string s;
   cin>>s;
   int n=s.size();
   s="?"+s;
   Hash.init(s);
   for(int i=n/2+1;i<n;i++){
     if(Hash.getHash1(1,i)==Hash.getHash1(n-i+1,n)&&Hash.getHash2(1,i)==Hash.getHash2(n-i+1,n))
      return cout<<"YES\n"<<s.substr(1,i)<<endl,void();
   }
   cout<<"NO\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}