单词检索(search)
\(Description\)
小可可是学校图书馆的管理员，现在他接手了一个十分棘手的任务。
由于学校需要一些材料，校长需要在文章中检索一些信息。校长一共给了小可可N篇文章，每篇文章为一个字符串。现在，校长需要他找到这样的单词，它至少在这N篇文章中的M篇文章里出现过，且单词长度为L。可是，工作量十分庞大，但校长又急需小可可完成这项任务。
现在他向你求助，需要你编写程序完成这项艰巨的任务。
\(Input\)
第1行3个正整数N，M，L，表示文章的数目，单词至少出现在M篇文章中和每个单词的长度。
接下来N行，每行一个字符串，表示一篇文章。
\(Output\)
仅一行，表示满足检索条件的单词数。
\(Sample Input\)
3 2 2
noip
istudycpp
imacppstudent
\(Sample Output\)
5
【样例解释】
这5个单词分别为：st，tu，ud，pp，cp。
\(Data Constraint\)
对于20%的数据有1≤N,M≤10；
对于60%的数据有1≤N,M≤100；
对于100%的数据有1≤N,M≤2000，L≤1000。每篇文章长度不大于1000，均有小写字母组成。
思路
字符串？
既然限定了答案字符的长度，那很容易想到分离字符串，统计出现个数
那就是 \(O(nl)\) 级别的个数，空间可以承受
然后怎么存分离出的字符
如果可以
对于每一篇文章，我们把分离的字符去重（因为答案要求的字符至少在N篇文章中的M篇文章里出现过）
最后合在一起
此时统计出现次数超过 \(M\) 的字符数量就是答案
想想，没有问题
关键是分离
如果把每个字符截取下来，那么一片文章处理的复杂度就是 \(O(|S|l)\)
\(n\) 篇就是 \(O(n|S|l)\) 的，显然不可以承受
然后呢？
正解
既然有了思路，那就直接打吧（也有 \(60\) 分了）
可是，现在是追求正解的时候
思路中的瓶颈在于分离字符
而我们知道要获取一段区间的信息，如果满足可加性，那就可以前缀和维护
字符串？
哦，哈希！
具体方式
对于一个字符串，我们对其进行哈希时，考虑映射成一个数字
一个很巧妙的方法是：把字符本身当做一串数字，一个字符对应权值
从高到低每一位的位权就参考十进制的方法，记作 \(B^{k-1}\)
其中 \(k\) 为第 \(k\) 位，\(B\) 是几进制
因为题中字符串均由小写字母构成
所以设为 \(26\) 进制（不这样也行，哈希映射的方法自己选择）
那么对于一个字符串S，有：
截取 S 中后 \(l\) 个字符组成的字符串设为 C'，前 \(|S| - l\) 个字符组成的字符串设为 C
则
于是维护 \(s_i =\sum_{k=1}^i H(|1...k|)\)
双模数，以防万一
代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL p1 = 1e9 + 7 , p2 = 1e9 + 9 , B = 26;
LL s1[1005] , s2[1005] , b1[1005] , b2[1005];
struct node{
LL x , y;
}d[2000005] , c[2000005];
int cnt , tot , n , m , l , ans;
char ch;
inline bool cmp(node a , node b){return (a.x < b.x || (a.x == b.x && a.y < b.y));}
int main()
{
scanf("%d%d%d" , &n , &m , &l);
b1[0] = b2[0] = 1;
for(register int i = 1; i <= 1001; i++) b1[i] = b1[i - 1] * B % p1;
for(register int i = 1; i <= 1001; i++) b2[i] = b2[i - 1] * B % p2;
int x;
for(register int i = 1; i <= n; i++)
{
x = 0 , s1[0] = 0 , s2[0] = 0 , cnt = 0;
ch = getchar();
while (ch < 'a' || ch > 'z') ch = getchar();
for(; ch >= 'a' && ch <= 'z'; ch = getchar())
{
x++;
s1[x] = (s1[x - 1] * B % p1 + (ch - 'a' + 1)) % p1;
s2[x] = (s2[x - 1] * B % p2 + (ch - 'a' + 1)) % p2;
if (x >= l)
{
d[++cnt].x = (s1[x] + p1 - s1[x - l] * b1[l] % p1) % p1;
d[cnt].y = (s2[x] + p2 - s2[x - l] * b2[l] % p2) % p2;
}
}
sort(d + 1 , d + cnt + 1 , cmp);
c[++tot] = d[1];
for(register int j = 2; j <= cnt; j++)
if (d[j].x != d[j - 1].x || d[j].y != d[j - 1].y)
c[++tot] = d[j];
}
sort(c + 1 , c + tot + 1 , cmp);
x = 1;
while (x <= tot)
{
int s = 1;
while (c[x].x == c[x + 1].x && c[x].y == c[x + 1].y && x < tot) x++ , s++;
if (s >= m) ans++;
x++;
}
printf("%d" , ans);
}