链接：P4421
【题目描述】
最近，某社交网络平台出现了用户信息的泄露。
Mihal 是一个喜欢探索计算机安全的学生，他发现整个事情非常有趣。在经过一段时间的研究，他发现了一个安全漏洞。当你输入任何字符串时，如果用户的密码在这个字符串中出现， 那么你就可以通过这个字符串成功登录。 例如，如果密码为 abc 的用户输入了一个字符串为 abc 或 abcdde 或 imaabcnema，他将会成功登录，而 axbc 则会登录失败。
现在 Mihal 想知道会出现多少次用户可以用自己的密码成功登录其他用户的情况。
【输入】
输入第一行为正整数 N，表示用户数量。（N<=20000）
接下来 N 行包含 N 个用户的密码，每个密码小写字母组成，长度不超过 10。
【输出】
输出共一行，输出出现用户可以用自己的密码成功登录其他用户的总次数。
【样例3解释】
第一个用户可以成功登录第二个用户和第三个用户，第二个用户可以成功登录第一个用户和第三个用户，第三个用户无法成功登录其他用户，总共出现 4 次本用户成功登录其他用户的情况。
输入输出样例
输入 #1
3
aaa
aa
abb
输出 #1
1
输入 #2
3
x
x
xy
输出 #2
4
输入 #3
5
mir
mirta
ta
ir
t
输出 #3
6
从题意可以看出，这道题需要求的是当前字符串在其他几个字符串中出现了几次
遇到字符串匹配我不会KMP，所以我们要使用哈希
根据数据范围
接下来 N 行包含 N 个用户的密码，每个密码小写字母组成，长度不超过 10。
所以我们可以枚举每一个子串的哈希值，这样我们就可以找到每一个大字符串所拥有的所有哈希值，加入序列A中，因为只有不超过10的字符串，所以这个模拟过程最多模拟55次
在我们找到每一个字符串的哈希值之后，我们在枚举每一个大字符串，算出这个大字符串的哈希值并且判断在序列A中有几个与其相同的哈希值就说明出现了几次
（注意：在一开始循环枚举子串的时候我们加入了这个大字符串，所以最后出现其他字符串了几次需要减一去掉包括自己字符串的次数）
但是
可能子串太多了！对于O（N平方*55）的复杂度这道题目完全过不去
所以我们在找子串哈希值与大字符串的哈希值匹配问题时，可以使用二分
将序列A从小到大排序
根据二分思想，如果当前这个哈希值大于A[mid]哈希值，则找右区间，否则就去找左区间。
这样时间复杂度就大幅度下降了。
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL c[90000001],b[90000001],tot,m;
int n,t;
char ch[20001][1001];
LL CZP(LL x)
{
LL L=1,R=m;
while (L<R)
{
LL mid=(L+R)>>1;
if (b[mid]<x) //如果这个b哈希值小于当前大字符串哈希值则去右区间
L=mid+1;
else
R=mid;
}
return L;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%s",ch[i]);
for (int i=1;i<=n;i++)
{
int s1=strlen(ch[i]);
int t1=0;
for (int t=1;t<=s1;t++)
{
for (int j=0;j<=s1-t;j++)
{
LL ans=1;
for (int v=j;v<=j+t-1;v++)
{
ans=(ans*26+(ch[i][v]-'a'+1)); //枚举每一个子串，把每一个子串的哈希值定义为26进制
}
c[++t1]=ans;
}
}
sort(c+1,c+t1+1); //排序更好去重
for (int j=1;j<=t1;j++)
if (c[j]!=c[j-1])
b[++m]=c[j]; //加入所有子串的序列中
//由于本题需要是找到在其他字符串中出现的次数
//所以每个字符串我们只需要找到一次一样的哈希值存储
}
sort(b+1,b+m+1); //排序进行二分查找
for (int i=1;i<=n;i++)
{
LL ans=1;
for (int j=0;j<strlen(ch[i]);j++)
ans=(ans*26+(ch[i][j]-'a'+1)); //找出当前大字符串的哈希值
LL x=CZP(ans); //进行二分
while (b[x]==ans)
{
tot++;
x++;
} //细节，可能会出现很多个，所以我们while循环再去右区间寻找一部分，我们在二分的时候将去左区间定义为R=mid这样就可以进行最后出现相同哈希值的次数枚举了
}
printf("%lld",tot-n); //减去自己的字符串次数
return 0;
}