/*
*
* 思路
* 利用后缀自动机求最长公共子串,如果只有两个字符串,求最长公共子串就直接先把第一个字符串构建成SAM,然后沿着第二个字符串对SAM做DFS遍历,
* 这是SAM的经典实用场景,在DFS过程里面,SAM中的节点可能会经过多次,每个节点里面需要有一个字段来维护经过这个节点之后的路径的长度,代表
* 的是这个节点的等价类子串集合中能够和外部匹配的最长的子串的长度,最后只要找每一个等价类节点中的最大的字段值即可,对于多个字符串的最长
* 公共子串问题求解,还是一样的做法,只不过每一个节点维护的字段变为多个,字段max_len_arr[i]表示第i轮DFS匹配中(也就是母串和第i个外部字符串的DFS匹配过程),
* 经过此节点时候,该节点的等价类子串集合中最长的和外部匹配的子串的长度,因为要求最长公共子串是要在每一个字符串里面都出现,所以每个节点
* 的等价类子串集合中,出现在了每一个原串的最长的子串长度应该是max_len_arr这个数组中的最小值,每一个SAM节点都取这个节点的max_len_arr数组
* 中的最小值,作为节点的特征值,最后答案就是所有节点的特征值的最大值
*
*
*/
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_NODE_NUM = 2000010; // 一般取字符串长度两倍
int tot = 1; // 当前总共的节点数
int last = 1; // 上一个已经构造出来的节点的编号,一开始有一个源点,编号为1
struct SamNode {
int len; // 节点代表的等价类子串集合中最长子串的长度
int fa; // 第二类边指针, 注意:如果没有后继,fa数值是1,不是0
int ch[26]; // 第一类边指针
int endpos_size; // 节点的endpos大小
int max_len_arr[10]; // max_len_arr[i]表示第i轮遍历中,经过此节点时候,该节点中最长的和外部匹配的子串的长度
} __node_pool[MAX_NODE_NUM];
// 第二类边反向边的邻接表
int h[MAX_NODE_NUM], e[MAX_NODE_NUM], ne[MAX_NODE_NUM], __edge_idx;
// 添加a指向b的边
void add_edge(int a, int b) {
e[__edge_idx] = b, ne[__edge_idx] = h[a], h[a] = __edge_idx++;
}
class SAM {
// 递归更新节点的endpos_size
void __dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
__dfs(e[i]);
__node_pool[u].endpos_size += __node_pool[e[i]].endpos_size;
}
}
public:
// 将字符c加入SAM中
void extend(int c) {
int p = last; // p表示上一个插入的节点
int np = last = ++tot; // 当前节点
__node_pool[tot].endpos_size = 1; // 新加入的点一定是包含了前缀的,初始化其endpos_size为1
__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].endpos_size = 0;
__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;
}
}
}
}
// 更新sam状态接口
void update_info() {
// 添加所有的第二类边的逆向边
memset(h, -1, sizeof(h));
__edge_idx = 0;
for (int i = 2; i <= tot; i++) {
add_edge(__node_pool[i].fa, i);
}
__dfs(1);
}
};
char s[10005];
// 返回匹配的深度
int dfs(int node_id, int str_pos, int str_len, int dfs_idx, int cur_dep, int& end_node_id) {
__node_pool[node_id].max_len_arr[dfs_idx] = max(__node_pool[node_id].max_len_arr[dfs_idx], cur_dep);
if (str_pos + 1 >= str_len) {
end_node_id = node_id;
return cur_dep;
}
int next = s[str_pos+1] - 'a';
if (__node_pool[node_id].ch[next] == 0) {
end_node_id = node_id;
return cur_dep;
}
return dfs(__node_pool[node_id].ch[next], str_pos+1, str_len, dfs_idx, cur_dep+1, end_node_id);
}
int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
int n;
scanf("%d", &n);
SAM algo;
// 从前到后向SAM中加入字符
scanf("%s", s);
for (int i = 0; s[i]; i++) {
algo.extend(s[i] - 'a');
}
algo.update_info();
for (int i = 0; i < n-1; i++) {
scanf("%s", s);
int str_len = strlen(s);
int pos = 0, node_id = 1;
while (pos < str_len) {
int c = s[pos] - 'a';
if (__node_pool[1].ch[c] == 0) {
pos += 1;
continue;
} else {
node_id = __node_pool[1].ch[c];
}
int dfs_dep = dfs(node_id, pos, str_len, i, 1, node_id);
// node_id这个点可能没有第二类边指向的后继,此时其fa值是1,下面语句也是没问题的,相当于pos += dfs_dep
pos += dfs_dep - (__node_pool[__node_pool[node_id].fa].len + 1) + 1;
}
}
int ans = 0;
for (int i = 2; i <= tot; i++) {
int min_val = 0x7fffffff;
for (int j = 0; j < n-1; j++) {
min_val = min(min_val, __node_pool[i].max_len_arr[j]);
}
ans = max(ans, min_val);
}
printf("%d\n", ans);
}
另一种写法
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_NODE_NUM = 100005 * 2; // 一般取字符串长度两倍
int tot = 1; // 当前总共的节点数
int last = 1; // 上一个已经构造出来的节点的编号,一开始有一个源点,编号为1
// 后缀自动机上的节点
struct SamNode {
int len; // 节点代表的等价类子串集合中最长子串的长度
int fa; // 第二类边指针
int ch[26]; // 第一类边指针
int endpos_size; // 节点的endpos大小
int match[10]; // match[i]表示第i轮遍历中,经过此节点时候,该节点中最长的和外部匹配的子串的长度
} __node_pool[MAX_NODE_NUM];
#define nodes __node_pool
long long ans;
#if __SAM_ENDPOS
set<int> endpos[MAX_NODE_NUM]; // 每个节点的endpos集合
#endif
#if __SAM_FIRST_POS
int first_pos[MAX_NODE_NUM]; // 每个节点endpos中的最小值
#endif
// 第二类边反向边的邻接表
int h[MAX_NODE_NUM], e[MAX_NODE_NUM], ne[MAX_NODE_NUM], __edge_idx;
// 添加a指向b的边
void add_edge(int a, int b) {
e[__edge_idx] = b, ne[__edge_idx] = h[a], h[a] = __edge_idx++;
}
class SAM {
// 递归更新节点的endpos_size
void __dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
__dfs(e[i]);
nodes[u].endpos_size += nodes[e[i]].endpos_size;
#if __SAM_ENDPOS
for (auto pos : endpos[e[i]]) {
endpos[u].insert(pos);
}
#endif
#if __SAM_FIRST_POS
first_pos[u] = min(first_pos[u], first_pos[e[i]]);
#endif
}
// 此处是利用SAM节点处理问题的代码,根据具体问题修改
ans += nodes[u].len;
// 此处是利用SAM节点处理问题的代码,根据具体问题修改
}
public:
SAM(int n) {
tot = 1;
last = 1;
__edge_idx = 0;
memset(h, -1, sizeof(int) * (n*2 + 1));
memset(nodes, 0, sizeof(SamNode) * (2*n+1));
}
// 将字符c加入SAM中
void extend(int c, int idx) {
int p = last; // p表示上一个插入的节点
int np = last = ++tot; // 当前节点
nodes[tot].endpos_size = 1; // 新加入的点一定是包含了前缀的,初始化其endpos_size为1, 其他情况新加的节点endpos_size初始值是0
#if __SAM_ENDPOS
endpos[tot].clear();
endpos[tot].insert(idx);
#endif
#if __SAM_FIRST_POS
first_pos[tot] = idx;
#endif
nodes[np].len = nodes[p].len + 1; // 新节点的最长子串的长度等于上一个节点的最长子串的长度加1
// 从上一个节点开始,枚举第二类边的祖先节点,直到祖先节点有c字符的第一类边为止,将所有这些祖先节点和新节点之间连接第一类边
for (; p && !nodes[p].ch[c]; p = nodes[p].fa) {
nodes[p].ch[c] = np;
}
// 如果所有祖先都没有c对应的第一类边,当前新节点和源点之间添加第二类边
if (!p) {
nodes[np].fa = 1;
} else {
int q = nodes[p].ch[c];
if (nodes[q].len == nodes[p].len + 1) {
// q节点作为新节点的第二类边的父亲
nodes[np].fa = q;
} else {
// 新建一个nq节点,作为新节点的第二类边的父亲
int nq = ++tot;
nodes[nq] = nodes[q];
nodes[nq].endpos_size = 0;
#if __SAM_ENDPOS
endpos[nq].clear();
#endif
#if __SAM_FIRST_POS
first_pos[tot] = 0x3f3f3f3f;
#endif
nodes[nq].len = nodes[p].len + 1;
nodes[q].fa = nodes[np].fa = nq;
for (; p && nodes[p].ch[c] == q; p = nodes[p].fa) {
nodes[p].ch[c] = nq;
}
}
}
}
// 更新sam状态接口
void update_info() {
// 添加所有的第二类边的逆向边
__edge_idx = 0;
for (int i = 2; i <= tot; i++) {
add_edge(nodes[i].fa, i);
}
__dfs(1);
}
};
void dfs(int idx, int dim_n) {
// 顺着第二类边做match的更新
for (int i = h[idx]; ~i; i = ne[i]) {
dfs(e[i], dim_n);
for (int j = 0; j < dim_n; j++) {
int val = min(nodes[idx].len, nodes[e[i]].match[j]);
nodes[idx].match[j] = max(nodes[idx].match[j], val);
}
}
}
char s[100005];
#define DEBUG_INPUT freopen("/Users/grh/Programming/CLionProjects/algo/input.txt", "r", stdin)
int main(void) {
//DEBUG_INPUT;
int n;
scanf("%d", &n);
// 从前到后向SAM中加入字符
scanf("%s", s);
SAM algo(strlen(s));
for (int i = 0; s[i]; i++) {
algo.extend(s[i] - 'a', i);
}
algo.update_info();
for (int i = 0; i < n-1; i++) {
scanf("%s", s);
int str_len = strlen(s);
int idx = 1, l = 0; // idx表示当前所在的状态点,l表示匹配长度
for (int ii = 0; ii < str_len; ii++) {
int val = s[ii] - 'a';
while (idx != 1 && nodes[idx].ch[val] == 0) {
idx = nodes[idx].fa;
l = nodes[idx].len;
}
if (nodes[idx].ch[val] != 0) {
idx = nodes[idx].ch[val];
l++;
nodes[idx].match[i] = max(nodes[idx].match[i], l);
}
}
}
// 更新所有点的match数组
dfs(1, n-1);
int ans = 0;
for (int i = 2; i <= tot; i++) {
int min_val = 0x7fffffff;
for (int j = 0; j < n-1; j++) {
min_val = min(min_val, __node_pool[i].match[j]);
}
ans = max(ans, min_val);
}
printf("%d\n", ans);
return 0;
}