P4421 [COCI2017-2018#1] Lozinke

题面:https://www.luogu.org/problem/P4421

本题把所有可能的子串全部做一遍字符串哈希,然后判断一波即可.
Code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
const int N=1000005;
int n,base=26,len;
long long hash[N],order[N],ans;
string a[N];
set<long long> Q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int num=0;
        for(int j=0;j<a[i].size();j++){
            long long Hash=a[i][j]-'a'+1;
            hash[++num]=Hash;
            for(int k=j+1;k<a[i].size();k++){
                Hash=Hash*base+a[i][k]-'a'+1;
                hash[++num]=Hash;
            }
        }
        sort(hash+1,hash+1+num);
        for(int j=1;j<=num;j++){
            if(hash[j]!=hash[j-1]){
                order[++len]=hash[j];
            }
        }
    }
    sort(order+1,order+1+len);
    for(int i=1;i<=n;i++){
        long long Hash=a[i][0]-'a'+1;
        for (int j=1;j<a[i].size();j++){
            Hash=Hash*base+a[i][j]-'a'+1;
        }
        int pos=lower_bound(order+1,order+1+len,Hash)-order;
        while(order[pos]==Hash){
            ans++;
            pos++;
        }
    }
    printf("%lld\n",ans-n);
    return 0;
}