2020牛客暑期多校训练营（第二场）A All with Pairs

All with Pairs

https://ac.nowcoder.com/acm/contest/5667/A

这题难点应该就是去重难想些吧

首先把每个字符串的后缀都hash了存到map里，然后从每个字符串遍历，从前到后，第i个字符串的第j个点字符，我们得到前缀的hash值是x，ans[i][j]=mp[x],然后ans[i][next[j]]-ans[i][j],这就是在去重，next就是kmp的next数组，最后答案是

具体描述下这个去重吧，应该会好理解点

就比如现在只有一个字符串ababa

从后往前存后缀
mp[a]=1;
mp[ba]=1;
mp[aba]=1;
mp[baba]=1;
mp[ababa]=1;

然后遍历前缀
ans[1]=mp[a]=1;
ans[2]=mp[ab]=0;
ans[3]=mp[aba]=1;
ans[4]=mp[abab]=0;
ans[5]=mp[ababa]=1;

然后从前往后
ans[next]-=ans[i]
最后就只有ans[5]=1了

为什么是ans[next]-=ans[i]呢？因为next已经存在于当前字符串里了，所以next要减去ans[i]

csdn 博客地址：https://blog.csdn.net/qq_43497140/article/details/107343259

#include<stdio.h>
#include<map>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 1050000
#define mod 998244353
ull base=131;
string a[maxn];
ull p[maxn];
map<ull,ull>mp;
ull ans[maxn];
ull kmp[maxn];
ull ans1[maxn];
void js(string b)
{
    ull j=0,lb=b.size()-1;
    for(int i=2;i<=lb;i++)
    {
        while(j&&b[i]!=b[j+1])
        {
            j=kmp[j];
        }
        if(b[i]==b[j+1]) j++;
        kmp[i]=j;
    }
    //for(ull i=1;i<=lb;i++) cout<<"kmp["<<i<<"]="<<kmp[i]<<'\n';
}
int main()
{
    ull n;
    cin>>n;
    p[0]=1;
    for(ull i=1;i<=maxn-10;i++)
    {
        p[i]=(p[i-1]*base);
    }
    for(ull i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=' '+a[i];
        ull len=a[i].size()-1;
        ull s=0;
        for(ull j=len;j>=1;j--)
        {
            s=p[len-j]*a[i][j]+s;
            mp[s]++;
            //cout<<"mp["<<s<<"]="<<mp[s]<<'\n';
        }
 
    }
    for(ull i=1;i<=n;i++)
    {
        ull len=a[i].size()-1;
        ull x=0,y=0;
        //cout<<"i="<<i<<'\n';
        js(a[i]);
 
        for(ull j=1;j<=len;j++)
        {
            x=x*base+a[i][j];
            y=p[j-1]*a[i][len-j+1]+y;
            //ans[j]+=mp[x];
            ans1[j]=mp[x];
            ans1[kmp[j]]-=ans1[j];
 
            //cout<<"mp["<<x<<"]="<<mp[x]<<'\n';
            //ans[j]-=(x==y);
        }
        for(ull j=1;j<=len;j++) ans[j]+=ans1[j];
    }
    ll w=0;
    for(ull i=1;i<=maxn-10;i++)
    {
        w+=i*i*ans[i];
        w%=mod;
        //cout<<"ans["<<i<<"]="<<ans[i]<<'\n';
    }
    cout<<w<<'\n';
}