小可可如何高效检索N篇文章中满足条件的单词？程序编写指南

ig281

[id_[]]

小可可是学校图书馆的管理员，此刻他承担了一项极为棘手的任务。

学校需要一些材料，所以校长要在文章中检索信息。校长给了小可可 N 篇文章，每篇都是一个字符串。现在校长需要他找出这样的单词，这个单词至少在 N 篇文章中的 M 篇里出现过，并且单词长度为 L。然而，工作量很大，但校长急需小可可完成这项任务。

现在他向你求助，需要你编写程序完成这项艰巨的任务。

样例输入：

3 个正整数 N、M、L 分别表示文章的数目、单词至少出现在的文章数以及每个单词的长度。

接下来N行，每行一个字符串，表示一篇文章。

3 2 2

noip

样例输出：

仅一行，表示满足检索条件的单词数

数据范围：

对于20%的数据有1≤N,M≤10；

对于60%的数据有1≤N,M≤100；

100%的数据满足 1≤N 且 1≤M 且 N≤2000 且 M≤2000，同时 L≤1000。每篇文章的长度不超过 1000，并且都是由小写字母构成的。

剖解题目

给出 n 个字符串，询问在其中至少 m 个字符串里出现过的长度为 l 的字符串的个数。

思路

一开始就想到hash，但坚定的相信这是水法。。。

虽然最终真的是水法

解法

20%：神奇的暴力。

60%：更神奇的暴力。n^2+kmp。

100%：

1.后缀数组，但是不会。。

2.强行hash。

开一个较大的素数（要有与素数的缘分），3千万左右。

当然，有爆空间的危险。。。。。。（原来有350M左右）。

为了节省空间，将数据类型进行了更改。原本是一个数组，改成 short int 类型后，空间减少了 50M。同时，还把 hash 值再取模后也改成了 short int 类型。经过这些操作，终于将空间卡到了 200M。

代码

<p><pre class="prettyprint">    <code class=" hljs cpp"><span class="hljs-preprocessor">#include<cstdio></span>
<span class="hljs-preprocessor">#include<algorithm></span>
<span class="hljs-preprocessor">#include<cstdlib></span>
<span class="hljs-preprocessor">#include<cstring></span>
<span class="hljs-preprocessor">#include<cmath></span>
<span class="hljs-preprocessor">定义一个宏 fo，它接受三个参数 i、a 和 b。这个宏的作用是创建一个 for 循环，循环变量 i 从 a 开始，每次递增 1，直到 i 小于 b 为止。在循环体内部，可以使用 i 进行相应的操作。<=b;i++)</span>
<span class="hljs-preprocessor">#define ll long long</span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn=<span class="hljs-number">2005</span>;
<span class="hljs-keyword">const</span> ll mo=<span class="hljs-number">28282789</span>,moo=<span class="hljs-number">31153</span>;
<span class="hljs-keyword">short</span> <span class="hljs-keyword">int</span> ha[mo+<span class="hljs-number">5</span>],n,m,len,bo[mo+<span class="hljs-number">5</span>],id;
<span class="hljs-keyword">short</span> <span class="hljs-keyword">int</span> ha2[mo+<span class="hljs-number">5</span>];
ll tmp[<span class="hljs-number">1005</span>];
ll ans;
<span class="hljs-keyword">char</span> s[maxn];
<span class="hljs-keyword">bool</span> bz[mo+<span class="hljs-number">10</span>];
<span class="hljs-keyword">int</span> hash(ll x)
{
    ll y=x%mo;
    <span class="hljs-keyword">while</span> (ha[y]!=x%moo&&ha[y]) y=y%mo+<span class="hljs-number">1</span>;
    <span class="hljs-keyword">if</span> (!ha[y]) ha[y]=x%moo;
    <span class="hljs-keyword">if</span> (bo[x]<id) ha2[y]++,bo[x]=id;
    <span class="hljs-keyword">return</span> y;
}
<span class="hljs-keyword">int</span> main()
{
    freopen(<span class="hljs-string">"T.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d%d%d"</span>,&n,&m,&len);
    tmp[len]=<span class="hljs-number">1</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=len-<span class="hljs-number">1</span>;i>=<span class="hljs-number">1</span>;i--) tmp=tmp[i+<span class="hljs-number">1</span>]*<span class="hljs-number">26</span>%mo;
    fo(i,<span class="hljs-number">1</span>,n){
        <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%s"</span>,s+<span class="hljs-number">1</span>);
        <span class="hljs-keyword">int</span> nowlen=<span class="hljs-built_in">strlen</span>(s+<span class="hljs-number">1</span>);
        <span class="hljs-keyword">if</span>(nowlen<len) <span class="hljs-keyword">continue</span>;
        ll value=<span class="hljs-number">0</span>;
        id++;
        fo(i,<span class="hljs-number">1</span>,len)
            value=(value+tmp*s)%mo;
        <span class="hljs-keyword">int</span> x=hash(value);
        <span class="hljs-keyword">if</span>如果 ha2[x] 大于等于 m 并且 bz[x] 为假，那么 ans 加 1，同时 bz[x] 赋值为真。<span class="hljs-keyword">true</span>;
        fo(i,len+<span class="hljs-number">1</span>,nowlen){
            <span class="hljs-keyword">int</span> pre=i-len;
            value=(((value-s[pre]*tmp[<span class="hljs-number">1</span>])%mo+mo)%mo*<span class="hljs-number">26</span>+s)%mo;
            x=hash(value);
            <span class="hljs-keyword">if</span> (ha2[x]>=m&&!bz[x]) ++ans,bz[x]=<span class="hljs-keyword">true</span>;
        }
    }
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%lld\n"</span>,ans);
} </code></pre></p>