题解 P4421 【 [COCI2017-2018#1] Lozinke】

lc_lca · 2020-01-29 23:02:14 · 题解

其实这道题远不用写进制版的hash

首先开个map<string,int>mp记录每个字符串的所有子串在几个串中出现。

例如说有个串abc就mp[a]++,mp[ab]++,mp[abc]++,mp[b]++,mp[bc]++,mp[c]++;

但是这就出问题了

假如一个串是aa那么mp[a]被加了两次，而一个子串只能对于当前串的贡献为1

所以用一个map<string,bool>tmp记录当前每个子串是否被加过，被加过就不再加了。

当然tmp在每一个串都要清零。

预计复杂度 20000 55 log20000

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
map<string,bool>tmp;
string s[20010];
int main()
{
    int n;
    scanf("%d",&n);
    mp.clear();
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        tmp.clear();
        int len=s[i].length();
        for(int k=1;k<=len;k++)
        {
            for(int j=k;j<=len;j++)
            {
                string t=s[i].substr(k-1,j-k+1);//截取子串，开头是k-1，长度是j-k+1
                if(tmp[t]==true)continue;
                tmp[t]=true;
                mp[t]++;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=mp[s[i]]-1;//统计
    }
    cout<<ans<<endl;
    return 0;
}