<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
给定 $n$ 个长度不超过 $50$ 的由小写英文字母组成的单词,以及一篇长为 $m$ 的文章。
请问,其中有多少个单词在文章中出现了。
注意:每个单词不论在文章中出现多少次,仅累计 $1$ 次。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
对于每组数据,第一行一个整数 $n$,接下去 $n$ 行表示 $n$ 个单词,最后一行输入一个字符串,表示文章。
输出格式
对于每组数据,输出一个占一行的整数,表示有多少个单词在文章中出现。
数据范围
$1 \\le n \\le 10^4$,
$1 \\le m \\le 10^6$
输入样例:
she
he
shr
her
yasherhs
输出样例:
3
思路
具体请见 $AC$ 自动机详解{:target=”_blank”}
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010,S = 55,M = 1000010;
int n;
int tr[N * S][26],cnt[N * S],idx;
int q[N * S],fail[N * S];
string str;
void insert (string s) { //Trie树的基本操作
int p = 0;
for (int i = 0;i < s.size ();i++) {
int x = s[i] - 'a';
if (!tr[p][x]) tr[p][x] = ++idx;
p = tr[p][x];
}
cnt[p]++;
}
void get_fail () {
int hh = 0,tt = -1; //由于Trie是一棵树,所以要用BFS
for (int i = 0;i < 26;i++) {
if (tr[0][i]) q[++tt] = tr[0][i]; //这里是把原来KMP中的0,1号点加入队列
}
while (hh <= tt) {
int t = q[hh++];
for (int i = 0;i < 26;i++) {
int &p = tr[t][i];
/*
if (p) {
int j = fail[t];
while (j && !tr[j][i]) j = fail[j]; //一直往前跳,知道某一个字符串的后一个字符是i
if (tr[j][i]) j = tr[j][i]; //对应KMP的if (s[i] == p[j + 1]) j++;
fail[p] = j; //求出next得知
q[++tt] = p;
}
*/
// 跳到父亲节点的fail指针,如果这个指针有字母i那么就和tr[t][i]相等了就可以直接把当前点赋值成tr[fail[t]][i],即父亲的失配指针的第i个儿子
if (!p) p = tr[fail[t]][i]; //直接跳到父节点的next指针的第i个儿子
else {
fail[p] = tr[fail[t]][i]; //求出fail的值
q[++tt] = p;
}
}
}
}
int main () {
int T;
cin >> T;
while (T--) {
memset (tr,0,sizeof (tr));
memset (cnt,0,sizeof (cnt));
memset (ne,0,sizeof (ne));
cin >> n;
for (int i = 1;i <= n;i++) {
string x;
cin >> x;
insert (x);
}
cin >> str;
get_fail ();
int ans = 0;
for (int i = 0,j = 0;i < str.size ();i++) {
int t = str[i] - 'a';
/*
while (j && !tr[j][t]) j = fail[j];
if (tr[j][t]) j = tr[j][t];
int p = j;
*/
int p = j = tr[j][t];
while (p) {
ans += cnt[p]; //这里要加上所有子序列的串,比如she中he也要算
cnt[p] = 0;
p = fail[p];
}
}
cout << ans << endl;
}
return 0;
}
一堆人被你带偏,写成get_fail,你不会分不清get和set吧
我这是学 y 总的,自己也不太懂,大佬能不能解释一下
get是取值,从类内“取出”某个成员变量的值使用,set是赋值,给类的某成员变量“赋予新值”,还有yxc可没错用get
yxc甚至根本没写get_fail
我个人认为 get_fail 可以译为获取 fail 的值,这里也挺符合
有想法也挺好,也许咱们只是因为还在求学,编程经验尚浅,等以后咱写的代码多了,经验丰富了,那就更能理解这些程序员们代代相传的命名习惯了