AcWing 1283. 玄武密码
原题链接
中等
作者:
皓首不倦
,
2021-05-14 04:20:56
,
所有人可见
,
阅读 447
/*
* 思路
* 母串构建SAM 然后再SAM上顺着前缀找最长子串即可
*
*/
#include <stdio.h>
#include <string.h>
using namespace std;
int char2idx(char ch) {
//return ch - 'A';
if (ch == 'E') {
return 0;
} else if (ch == 'S') {
return 1;
} else if (ch == 'W') {
return 2;
} else {
return 3;
}
}
const int MAX_NODE_NUM = 20000007; // 一般取字符串长度两倍
int tot = 1; // 当前总共的节点数
int last = 1; // 上一个已经构造出来的节点的编号,一开始有一个源点,编号为1
// 后缀自动机上的节点
struct SamNode {
int len; // 节点代表的等价类子串集合中最长子串的长度
int fa; // 第二类边指针
int ch[4]; // 第一类边指针
} __node_pool[MAX_NODE_NUM];
char s[10000007];
char seg[105];
class SAM {
public:
// 将字符c加入SAM中
void extend(int c) {
int p = last; // p表示上一个插入的节点
int np = last = ++tot; // 当前节点
__node_pool[np].len = __node_pool[p].len + 1; // 新节点的最长子串的长度等于上一个节点的最长子串的长度加1
// 从上一个节点开始,枚举第二类边的祖先节点,直到祖先节点有c字符的第一类边为止,将所有这些祖先节点和新节点之间连接第一类边
for (; p && !__node_pool[p].ch[c]; p = __node_pool[p].fa) {
__node_pool[p].ch[c] = np;
}
// 如果所有祖先都没有c对应的第一类边,当前新节点和源点之间添加第二类边
if (!p) {
__node_pool[np].fa = 1;
} else {
int q = __node_pool[p].ch[c];
if (__node_pool[q].len == __node_pool[p].len + 1) {
// q节点作为新节点的第二类边的父亲
__node_pool[np].fa = q;
} else {
// 新建一个nq节点,作为新节点的第二类边的父亲
int nq = ++tot;
__node_pool[nq] = __node_pool[q];
__node_pool[nq].len = __node_pool[p].len + 1;
__node_pool[q].fa = __node_pool[np].fa = nq;
for (; p && __node_pool[p].ch[c] == q; p = __node_pool[p].fa) {
__node_pool[p].ch[c] = nq;
}
}
}
}
};
void dfs(int str_pos, int max_pos, int sam_node, int& dep) {
if (str_pos+1 == max_pos) {
return;
}
char c = seg[str_pos+1];
if (__node_pool[sam_node].ch[char2idx(c)]) {
dep++;
dfs(str_pos+1, max_pos, __node_pool[sam_node].ch[char2idx(c)], dep);
}
}
int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
scanf("%s", s);
int str_len = strlen(s);
SAM algo;
for (int i = 0; i < str_len; i++) {
algo.extend(char2idx(s[i]));
}
int ans;
for (int i = 0; i < m; i++) {
ans = 0;
scanf("%s", seg);
dfs(-1, strlen(seg), 1, ans);
printf("%d\n", ans);
}
return 0;
}