|
|
[id[[]6[]]
学校需要一些材料，所以校长要在文章中检索信息。校长给了小可可 N 篇文章，每篇都是一个字符串。现在校长需要他找出这样的单词，这个单词至少在 N 篇文章中的 M 篇里出现过，并且单词长度为 L。然而，工作量很大，但校长急需小可可完成这项任务。
现在他向你求助，需要你编写程序完成这项艰巨的任务。
数据中 100%的情况是 1≤N 且 1≤M 且 N≤2000 且 M≤2000，同时 L≤1000。每一篇文章的长度都不大于 1000，并且这些文章均由小写字母组成。
1 字符串哈希
因为字符串长度为L不变，所以动态更新哈希值
记得要先模一个大一点的数，如果太小容易重复导致出错
记录哈希值的时候把它模得小一点。之所以可以模得小一点，是因为只需要将其存起来，而不需要进行比较。
为了更优美最好弄双哈希，我单哈希过掉了
2 SA
——by lau
把所有串连起来，各个串中间用各不相同的特殊符号连起来
对于将大于等于 L 的分成一段的情况，需要判断每一段内是否存在多于 m 个元素出现在不同的串里。
Code
<p><pre class="prettyprint"> <code class=" hljs perl"><span class="hljs-comment">#include<cstdio></span>
<span class="hljs-comment">#include<cstring></span>
<span class="hljs-comment">#include<algorithm></span>
<span class="hljs-comment">定义一个宏 fo，它接受三个参数 i、a 和 b。这个宏的作用是创建一个 for 循环，循环变量 i 从 a 开始，每次递增 1，直到 i 小于 b 为止。在循环体内部，可以使用 i 进行相应的操作。<=b;i++)</span>
using namespace std;
typedef long long ll;
const <span class="hljs-keyword">int</span> N=<span class="hljs-number">2005</span>;
const ll mo=<span class="hljs-number">1</span>e9+<span class="hljs-number">7</span>,hx=<span class="hljs-number">5000000</span>;
<span class="hljs-keyword">int</span> n,<span class="hljs-keyword">m</span>,l,h[hx][<span class="hljs-number">3</span>];
ll _26,a[N];
char <span class="hljs-keyword">s</span>[N];
<span class="hljs-keyword">int</span> hash(<span class="hljs-keyword">int</span> <span class="hljs-keyword">x</span>)
{
<span class="hljs-keyword">int</span> <span class="hljs-keyword">pos</span>=<span class="hljs-keyword">x</span><span class="hljs-variable">%hx</span>;
<span class="hljs-keyword">while</span>(h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">0</span>] && h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">0</span>]!=<span class="hljs-keyword">x</span>) <span class="hljs-keyword">pos</span>=(<span class="hljs-keyword">pos</span>+<span class="hljs-number">1</span>)<span class="hljs-variable">%hx</span>;
h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">0</span>]=<span class="hljs-keyword">x</span>;
<span class="hljs-keyword">return</span> <span class="hljs-keyword">pos</span>;
}
<span class="hljs-keyword">int</span> main()
{
<span class="hljs-keyword">int</span> <span class="hljs-number">_</span>,ans=<span class="hljs-number">0</span>;
scanf(<span class="hljs-string">"<span class="hljs-variable">%d</span> <span class="hljs-variable">%d</span> <span class="hljs-variable">%d</span>\n"</span>,&<span class="hljs-number">_</span>,&<span class="hljs-keyword">m</span>,&l);
_26=<span class="hljs-number">1</span>;
fo(i,<span class="hljs-number">1</span>,l) _26=_26<span class="hljs-variable">*26</span><span class="hljs-variable">%mo</span>;
<span class="hljs-keyword">while</span>(<span class="hljs-number">_</span>--)
{
scanf(<span class="hljs-string">"<span class="hljs-variable">%s</span>\n"</span>,<span class="hljs-keyword">s</span>+<span class="hljs-number">1</span>);
n=strlen(<span class="hljs-keyword">s</span>+<span class="hljs-number">1</span>);
<span class="hljs-keyword">if</span>(n<l) <span class="hljs-keyword">continue</span>;
fo(i,<span class="hljs-number">1</span>,n)
{
a=(a[i-<span class="hljs-number">1</span>]<span class="hljs-variable">*26</span>+<span class="hljs-keyword">s</span>-<span class="hljs-string">'a'</span>+<span class="hljs-number">1</span>)<span class="hljs-variable">%mo</span>;
<span class="hljs-keyword">if</span>(i>=l)
{
<span class="hljs-keyword">if</span>(i>l) a=(a-(<span class="hljs-keyword">s</span>[i-l]-<span class="hljs-string">'a'</span>+<span class="hljs-number">1</span>)<span class="hljs-variable">*_26</span><span class="hljs-variable">%mo</span>+mo)<span class="hljs-variable">%mo</span>;
<span class="hljs-keyword">int</span> <span class="hljs-keyword">pos</span>=hash(a);
<span class="hljs-keyword">if</span>(h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">2</span>]==<span class="hljs-number">_</span>) <span class="hljs-keyword">continue</span>;
<span class="hljs-keyword">if</span>(++h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">1</span>]==<span class="hljs-keyword">m</span>) ans++;
h[<span class="hljs-keyword">pos</span>][<span class="hljs-number">2</span>]=<span class="hljs-number">_</span>;
}
}
}
<span class="hljs-keyword">printf</span>(<span class="hljs-string">"<span class="hljs-variable">%d</span>"</span>,ans);
<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}</code></pre></p> |
|
发表于 2025-4-22 07:12:51