2019-team-666-paste

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include<bits/stdc++.h>
#define ull unsigned long long
#define pll pair<ull,ull>
using namespace std;
map<pll,int> mp[200005];
vector<char> v[200005];
char s[200005],t[200005];
bool vis[200005];
int len[200005],n,m;
ull p[200005],base1=233,base2=1091,hsh1[200005],hsh2[200005],nhsh2[200005],nhsh1[200005],mod1=1000000009,mod2=998244353,p1[200005],p2[200005];
pll gethash(int l,int r)
{
    if(l>r)
        return pll(0,0);
    return pll(((hsh1[r]-hsh1[l-1]*p1[r-l+1]%mod1)+mod1)%mod1,((hsh2[r]-hsh2[l-1]*p2[r-l+1]%mod2)+mod2)%mod2);
}
pll newhash(int l,int r)
{
    if(l>r)
        return pll(0,0);
    return pll(((nhsh1[r]-nhsh1[l-1]*p1[r-l+1]%mod1)+mod1)%mod1,((nhsh2[r]-nhsh2[l-1]*p2[r-l+1]%mod2)+mod2)%mod2);
}
pll operator + (pll x,pll y)
{
    return pll((x.first+y.first)%mod1,(x.second+y.second)%mod2);
}
pll operator * (pll x,int y)
{
    return pll(x.first*p1[y]%mod1,x.second*p2[y]%mod2);
}
int main()
{
    int T=3;
    cin>>T;
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%s",t+1);
            len[i]=strlen(t+1);
            vis[len[i]]=1;
            for(int j=1;j<=len[i];j++)
            {
                v[i].push_back(t[j]);
            }
        }
        p1[0]=p2[0]=1;
        for(int i=1;i<=n;i++)
        {
            p1[i]=p1[i-1]*base1%mod1;
            p2[i]=p2[i-1]*base2%mod2;
            hsh1[i]=hsh1[i-1]*base1%mod1+(s[i]-'a'+1);
            if(hsh1[i]>=mod1) hsh1[i]-=mod1;
            hsh2[i]=hsh2[i-1]*base2%mod2+(s[i]-'a'+1);
            if(hsh2[i]>=mod2) hsh2[i]-=mod2;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
            {
                for(int j=i;j<=n;j++)
                {
                    mp[i][gethash(j-i+1,j)]++;
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            nhsh1[0]=nhsh2[0]=0;
            int ans=0;
            for(int j=1;j<=v[i].size();j++)
            {
                nhsh1[j]=nhsh1[j-1]*base1%mod1+(v[i][j-1]-'a'+1);
                if(nhsh1[j]>=mod1) nhsh1[j]-=mod1;
                nhsh2[j]=nhsh2[j-1]*base2%mod2+(v[i][j-1]-'a'+1);
                if(nhsh2[j]>=mod2) nhsh2[j]-=mod2;
            }
            for(int j=1;j<=len[i];j++)
            {
                for(int k=1;k<=26;k++) 
                {
                    if(k==v[i][j-1]-'a'+1) 
                        continue;

                    pll temp=newhash(j+1,len[i])+newhash(1,j-1)*(len[i]-j+1)+pll(p1[len[i]-j]*(k),p2[len[i]-j]*k);
                    //cout<<p[len[i]-j]<<" "<<len[i]<<endl; 
                    //cout<<temp<<endl; 
                    ans+=mp[len[i]][temp];
                }
            } 
            //cout<<nhsh[len[i]]<<" "<<hsh[len[i]]<<endl; 
            ans+=mp[len[i]][pll(nhsh1[len[i]],nhsh2[len[i]])];
            printf("%d\n",ans);
        } 
        for(int i=1;i<=n;i++) 
        {
            if(vis[i]) 
                mp[i].clear();
        }
        for(int i=1;i<=m;i++) 
        {
            vis[len[i]]=0; 
            v[i].clear();
        }
    } 
    return 0;
}
/*
1
abcdefghij
2
abd
a
*/

#include

#define ull unsigned long long

#define pll pair

using namespace std;

map mp[200005];

vector v[200005];

char s[200005],t[200005];

bool vis[200005];

int len[200005],n,m;

ull p[200005],base1=233,base2=1091,hsh1[200005],hsh2[200005],nhsh2[200005],nhsh1[200005],mod1=1000000009,mod2=998244353,p1[200005],p2[200005];

pll gethash(int l,int r)

{

if(l>r)

return pll(0,0);

return pll(((hsh1[r]-hsh1[l-1]*p1[r-l+1]%mod1)+mod1)%mod1,((hsh2[r]-hsh2[l-1]*p2[r-l+1]%mod2)+mod2)%mod2);

}

pll newhash(int l,int r)

{

if(l>r)

return pll(0,0);

return pll(((nhsh1[r]-nhsh1[l-1]*p1[r-l+1]%mod1)+mod1)%mod1,((nhsh2[r]-nhsh2[l-1]*p2[r-l+1]%mod2)+mod2)%mod2);

}

pll operator + (pll x,pll y)

{

return pll((x.first+y.first)%mod1,(x.second+y.second)%mod2);

}

pll operator * (pll x,int y)

{

return pll(x.first*p1[y]%mod1,x.second*p2[y]%mod2);

}

int main()

{

int T=3;

cin>>T;

while(T--)

{

scanf("%s",s+1);

n=strlen(s+1);

scanf("%d",&m);

for(int i=1;i<=m;i++)

{

scanf("%s",t+1);

len[i]=strlen(t+1);

vis[len[i]]=1;

for(int j=1;j<=len[i];j++)

{

v[i].push_back(t[j]);

}

}

p1[0]=p2[0]=1;

for(int i=1;i<=n;i++)

{

p1[i]=p1[i-1]*base1%mod1;

p2[i]=p2[i-1]*base2%mod2;

hsh1[i]=hsh1[i-1]*base1%mod1+(s[i]-'a'+1);

if(hsh1[i]>=mod1) hsh1[i]-=mod1;

hsh2[i]=hsh2[i-1]*base2%mod2+(s[i]-'a'+1);

if(hsh2[i]>=mod2) hsh2[i]-=mod2;

}

for(int i=1;i<=n;i++)

{

if(vis[i])

{

for(int j=i;j<=n;j++)

{

mp[i][gethash(j-i+1,j)]++;

}

}

}

for(int i=1;i<=m;i++)

{

nhsh1[0]=nhsh2[0]=0;

int ans=0;

for(int j=1;j<=v[i].size();j++)

{

nhsh1[j]=nhsh1[j-1]*base1%mod1+(v[i][j-1]-'a'+1);

if(nhsh1[j]>=mod1) nhsh1[j]-=mod1;

nhsh2[j]=nhsh2[j-1]*base2%mod2+(v[i][j-1]-'a'+1);

if(nhsh2[j]>=mod2) nhsh2[j]-=mod2;

}

for(int j=1;j<=len[i];j++)

{

for(int k=1;k<=26;k++)

{

if(k==v[i][j-1]-'a'+1)

continue;

pll temp=newhash(j+1,len[i])+newhash(1,j-1)*(len[i]-j+1)+pll(p1[len[i]-j]*(k),p2[len[i]-j]*k);

//cout<

//cout<

ans+=mp[len[i]][temp];

}

}

//cout<

ans+=mp[len[i]][pll(nhsh1[len[i]],nhsh2[len[i]])];

printf("%d\n",ans);

}

for(int i=1;i<=n;i++)

{

if(vis[i])

mp[i].clear();

}

for(int i=1;i<=m;i++)

{

vis[len[i]]=0;

v[i].clear();

}

}

return 0;

}

/*

1

abcdefghij

2

abd

a

*/