简单字符串哈希
题意
给一个字符串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 regionals multiply contest problem permutation codeforces another problem problem contest文件2928 permutation codeforces problem version codeforces problem matrix 1913e codeforces problem round 761 periodicity regionals contest problem contest problem 20035 http