题解：AT_agc047_b [AGC047B] First Second

· · 题解

使用哈希可以水过大部分字符串题

思路

假设现有两个字符串 S1 与 S2，其中 S1 的长度更短。那么，若这两个字符串要满足要求，则 S1 除第一个字符外的其他字符做组成的串需要是 S2 的后缀，且 S1 的第一个字符要在 S2 除开之前那个后缀的其余部分出现。

换个说法：若 S1 由字符 c1 与字符串 s1 组成，S2 由字符串 s2 与字符串 s3 组成，若这两个字符串要满足要求，则需要满足 s1 与 s3 相等，且 c1 要在 s2 中出现。

于是我们就可以来完成这道题了。先将所有串按长度大小从小到大排个序。对于每个串，枚举它的所有后缀，对于每个后缀，我们用一个map存储其能与哪些字符拼成先前出现了的长度更短的字符串，然后再用一个标记看这些字符是否在这个字符串除开当前后缀的地方出现过就行了。统计完答案后，再将该字符串加入map就行了。

其中，取后缀需要用哈希优化一下，因为直接substr的复杂度是 O(n) 的，会超时。另外，再记得特判一下长度为 1 的情况。具体细节请参考代码。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=2e5+5,M=1e6+5;
int n,m,bjt[123],ans;
string s[N];
map<ull,string>mp;
ull p[M],P[M];
ull hp(int l,int r){return p[r]-p[l-1]*P[r-l+1];}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    P[0]=1,P[1]=131;
    for(int i=2;i<M;i++)P[i]=P[i-1]*P[1];
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+n+1,[](string i,string j){return i.size()<j.size();});
    for(int i=1;i<=n;i++){
        m=s[i].size(),p[0]=s[i][0];
        for(int j=1;j<m;j++)
            p[j]=p[j-1]*P[1]+s[i][j];
        memset(bjt,0,sizeof bjt);
        for(int j=0;j<m;j++){
            if(j>0){
                string tmp=mp[hp(j,m-1)];
                for(int k=0;k<tmp.size();k++)
                    ans+=bjt[tmp[k]];
            }
            bjt[s[i][j]]=1;
        }
        string tmp=mp[0];
        for(int k=0;k<tmp.size();k++)ans+=bjt[tmp[k]];
        mp[(m>1?hp(1,m-1):0)]+=s[i][0];
    }
    cout<<ans;
    return 0;
}

AC记录