简单字符串哈希
题意
给一个字符串s和t,问从s的某个位置开始,向右到某个点后再向左,顺序遍历到的字符形成的字符串可否为t。
思路
数据只有500,\(O(n^3)\)可过,枚举转折点,然后枚举开头和结尾。
代码
int n,m,k;
ull Hash[1010],rHash[1010],p[1010],rp[1010],sum;
void solve()
{
string s,t;
cin>>s>>t;
n=s.size(),m=t.size();
s=" "+s,t=" "+t;
p[0]=1;
sum=0;
for(int i=1;i<=m;i++) sum=sum*M+t[i];
for(int i=1;i<=n;i++)
{
Hash[i]=Hash[i-1]*M+s[i];
p[i]=p[i-1]*M;
}
rp[n+1]=1;
rHash[n+1]=0;
for(int i=n;i>=1;i--)
{
rHash[i]=rHash[i+1]*M+s[i];
}
for(int k=(m+1)/2;k<=n;k++)
{
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
if(k-i+1+k-j!=m) continue;
ull x = Hash[k]-Hash[i-1]*p[k-i+1];
ull y = rHash[j]- rHash[k]*p[k-j];
ull z = x*p[k-j]+y;
if(z==sum) {cout<<"YES\n";return;}
}
}
}
cout<<"NO\n";
}
- codeforces contest problem 1553 comcodeforces contest problem 1553 codeforces backspace 1553d cf contest problem 20035 http problems atcoder regular contest periodicity regionals contest problem permutation codeforces another problem regionals multiply contest problem permutation codeforces problem 1909i codeforces problem matrix 1913e problem contest文件2928