简单字符串哈希
题意
给一个字符串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 periodicity regionals contest problem educational codeforces contest round codeforces contest round https codeforces 103119b problem boring permutation codeforces problem version