https://vjudge.net/problem/LightOJ-1427
把所有模式串加入ac自动机，然后search的时候暴力，每个子串都暴力一下就好。
其实AC自动机就是，先建立好trie图。预处理加速查找
然后查找有多少个模式串的时候，相当于一个暴力，
每一次循环，其实就是枚举文本串的每一个位置，以它为结尾的子串中，有多少个出现在模式串中。
直接做是要枚举每一个模式串，AC自动机就把这个步骤简化为Fail指针了。用fail指针查找。
相当于，查找str[1...i] str[2...i] , str[3....i].....srt[i, i]是否在模式串中
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
typedef unsigned long long int ULL;
const int maxn = 5e2 + ;
char sub[maxn][maxn], str[ + ];
int len[maxn];
const int N = ;
struct node {
int flag;
struct node *Fail; //失败指针，匹配失败，跳去最大前后缀
struct node *pNext[N];
} tree[maxn * maxn];
int t; //字典树的节点
struct node *create() { //其实也只是清空数据而已，多case有用，根是0号顶点、
struct node *p = &tree[t++];
p->flag = ;
p->Fail = NULL;
for (int i = ; i < N; i++) {
p->pNext[i] = NULL;
}
return p;
}
void insert(struct node **T, char str[], int id) {
struct node *p = *T;
if (p == NULL) {
p = *T = create();
}
for (int i = ; str[i]; i++) {
int id = str[i] - 'a';
if (p->pNext[id] == NULL) {
p->pNext[id] = create();
}
p = p->pNext[id];
}
p->flag = id; //相同的单词算两次
}
void BuiltFail(struct node **T) {
//根节点没有失败指针,所以都是需要特判的
//思路就是去到爸爸的失败指针那里，找东西匹配，这样是最优的
struct node *p = *T; //用个p去代替修改
struct node *root = *T;
if (p == NULL) return ;
//树上bfs,要更改的是p->pNext[i]->Fail
struct node *que[t + ]; //这里的t是节点总数，字典树那里统计的，要用G++编译
int head = , tail = ;
que[tail++] = root;
while (head < tail) {
p = que[head]; //p取出第一个元素 ★
for (int i = ; i < N; i++) { //看看存不存在这个节点
if (p->pNext[i] != NULL) { //存在的才需要管失败指针。
if (p == root) { //如果爸爸是根节点的话，根节点没有失败指针
p->pNext[i]->Fail = root; //指向根节点
} else {
struct node *FailNode = p->Fail; //首先找到爸爸的失败指针
while (FailNode != NULL) {
if (FailNode->pNext[i] != NULL) { //存在
p->pNext[i]->Fail = FailNode->pNext[i];
break;
}
FailNode = FailNode->Fail; //回溯，根节点的fail是NULL
}
if (FailNode == NULL) { //如果还是空，那么就指向根算了
p->pNext[i]->Fail = root;
}
}
que[tail++] = p->pNext[i]; //这个id是存在的，入队bfs
} else if (p == root) { //变化问题，使得不存在的边也建立起来。
p->pNext[i] = root;
} else {
p->pNext[i] = p->Fail->pNext[i]; //变化到LCP。可以快速匹配到病毒。
//就是在p这个节点上，再增加一个点pNext[i]，就是不合法串。
}
}
head++;
}
}
ULL val[maxn];
int ans[maxn];
void calc(struct node *T) {
struct node * p = T;
struct node * root = T;
if (p == NULL) return;
for (int i = ; str[i]; ++i) {
int id = str[i] - 'a';
p = p->pNext[id];
struct node *temp = p;
while (temp != root) {
if (temp->flag) ans[temp->flag]++;
temp = temp->Fail;
}
}
}
void work() {
t = ;
int n;
scanf("%d", &n);
scanf("%s", str + );
int lenstr = strlen(str + );
struct node *T = NULL;
for (int i = ; i <= n; ++i) {
scanf("%s", sub[i] + );
len[i] = strlen(sub[i] + );
insert(&T, sub[i], i);
ULL fuck = ;
for (int j = ; j <= len[i]; ++j) {
fuck = fuck * + sub[i][j];
}
val[i] = fuck;
}
BuiltFail(&T);
memset(ans, false, sizeof ans);
calc(T);
// printf("%d\n", val[1] == val[3]);
for (int i = ; i <= n; ++i) {
for (int j = i + ; j <= n; ++j) {
if (val[i] == val[j]) ans[i] = ans[j] = max(ans[i], ans[j]);
}
}
static int f = ;
printf("Case %d:\n", ++f);
for (int i = ; i <= n; ++i) {
printf("%d\n", ans[i]);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
其实sam每一次也就O(lensub)复杂度，所以总复杂度是500 * 500的
但是不行，MLE
烦。感觉sam被卡内存很严重
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 2e6 + , N = ;
struct Node {
int mxCnt; //mxCnt表示后缀自动机中当前节点识别子串的最大长度
int miCnt; //miCnt表示后缀自动机中当前节点识别子串的最小长度
int id; //表示它是第几个后缀自动机节点，指向了它，但是不知道是第几个，用id判断
bool flag; //表示当前节点是否能识别前缀
struct Node *pNext[N], *fa;
}suffixAutomaton[maxn], *root, *last; //大小需要开2倍，因为有一些虚拟节点
int t; //用到第几个节点
struct Node *create(int mxCnt = -, struct Node *node = NULL) { //新的节点
if (mxCnt != -) {
suffixAutomaton[t].mxCnt = mxCnt, suffixAutomaton[t].fa = NULL;
for (int i = ; i < N; ++i) suffixAutomaton[t].pNext[i] = NULL;
} else {
suffixAutomaton[t] = *node; //保留了node节点所有的指向信息
//可能需要注意下pos，在原串中的位置。现在pos等于原来node的pos
}
suffixAutomaton[t].id = t; //必须要有的，不然id错误
suffixAutomaton[t].flag = false;
return &suffixAutomaton[t++];
}
void addChar(int x, int pos) { //pos表示在原串的位置
struct Node *p = last, *np = create(p->mxCnt + , NULL);
np->flag = true;
last = np; //last是最尾那个可接收后缀字符的点。
for (; p != NULL && p->pNext[x] == NULL; p = p->fa) p->pNext[x] = np;
if (p == NULL) {
np->fa = root;
np->miCnt = ; // 从根节点引一条边过来
return;
}
struct Node *q = p->pNext[x];
if (q->mxCnt == p->mxCnt + ) { //中间没有任何字符
np->fa = q;
np->miCnt = q->mxCnt + ; // q是7-->8的那些"ab"，np是"bab"长度是2+1
return;
}
// p： 当前往上爬到的可以接受后缀的节点
// np：当前插入字符x的新节点
// q： q = p->pNext[x]，q就是p中指向的x字符的节点
// nq：因为q->cnt != p->cnt + 1而新建出来的模拟q的节点
struct Node *nq = create(-, q); // 新的q节点，用来代替q，帮助np接收后缀字符
nq->mxCnt = p->mxCnt + ; //就是需要这样，这样中间不包含任何字符
q->miCnt = nq->mxCnt + , np->miCnt = nq->mxCnt + ;
q->fa = nq, np->fa = nq; //现在nq是包含了本来q的所有指向信息
for (; p && p->pNext[x] == q; p = p->fa) {
p->pNext[x] = nq;
}
}
void init() {
t = ;
root = last = create(, NULL);
}
void build(char str[], int lenstr) {
init();
for (int i = ; i <= lenstr; ++i) {
addChar(str[i] - 'a', i);
}
}
char str[maxn];
int lenstr;
int in[maxn];
int dp[maxn];
int que[maxn];
int ans[maxn];
char sub[maxn];
const int MOD = 1e9 + ;
void work() {
int n;
scanf("%d", &n);
scanf("%s", str + );
lenstr = strlen(str + );
build(str, lenstr);
for (int i = ; i < t; ++i) {
in[suffixAutomaton[i].fa->id]++;
if (suffixAutomaton[i].flag) dp[i] = ;
else dp[i] = ;
}
int head = , tail = ;
for (int i = ; i < t; ++i) {
if (in[i] == ) que[tail++] = i;
}
while (head < tail) {
int cur = que[head++];
if (!cur) break;
dp[suffixAutomaton[cur].fa->id] += dp[cur];
in[suffixAutomaton[cur].fa->id]--;
if (in[suffixAutomaton[cur].fa->id] == ) que[tail++] = suffixAutomaton[cur].fa->id;
}
static int f = ;
printf("Case %d:\n", ++f);
dp[] = ;
while (n--) {
scanf("%s", sub + );
int now = ;
for (int i = ; sub[i]; ++i) {
if (!suffixAutomaton[now].pNext[sub[i] - 'a']) {
now = ;
break;
}
now = suffixAutomaton[now].pNext[sub[i] - 'a']->id;
}
printf("%d\n", dp[now]);
}
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--)
work();
return ;
}