POJ2774 –后缀树解法
POJ2774 Long Long Message –后缀树解法
题意明确说明求两字符串的最长连续公共子串，可用字符串hash或者后缀数据结构来做
关于后缀树
后缀树的原理较为简单，但 \(o(n)\) 的构建算法（Ukkonen算法）稍难理解，可参考以下博文
//www.cnblogs.com/xubenben/p/3484988.html
- 在此也特别感谢该作者，本人也参考了上述文章作者的讲解，可以从我后面的代码看出和作者的代码步骤是一样的。我的代码主要体现的是对本题的dfs阶段的处理
思路
-
1.获得两个字符串ss1,ss2之后，将其拼接为\(ss1\) + “{” + \(ss1\) + “|”,之所以选择这两个字符是因为其ascii码紧跟在’z’之后，对存储空间较为友好
-
2.对合串建立后缀树
-
3.遍历后缀树，记录经过的字符串长度，对找到一个经过的长度最长的非叶子节点，这个节点要同时满足：
- 有一个子树中包含{（当然这样的话必然包含|），说明这个节点属于ss1
- 有一个子树中包含|（并且不包含{），说明这个节点属于ss2
同时满足，说明从根到此节点的路程，经过的全是公共子串，可以根据记录的字符串长度更新答案
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = (1 << 30);
const int root = 1;
char ss[200010] = {0};
char ss2[100005] = {0};
int act = 1, co = 1;
int acteg = -1;
int tep = 0;
int ind = 0, rem = 0, s_end = -1;
int links[100005] = {0};
int vv[100005] = {0};
int mm = 0;
int linkk = 0;
int len1 = 0, len2 = 0;
int ans = 0; //本题答案
struct ab
{
int l;
int r;
int nex;
int alp[28]; // 后面26 27 下标代表的字符是 ‘{’和 ‘|’
} tree[1000005]; // 作为分割与结束符 (ascii相邻防止越界)
int add_new(int o, int ll = s_end, int rr = maxn)
{
tree[o].l = ll;
tree[o].r = rr;
return o;
}
void add_link(int o)
{
if (linkk)
{
tree[linkk].nex = o;
}
linkk = o;
}
int check_len(int o)
{
return min(tree[o].r, s_end) - tree[o].l + 1;
}
bool check_contain(int o)
{
int node_len = check_len(o);
if (node_len <= ind)
{
ind -= node_len;
tep += node_len;
act = o;
return true;
}
return false;
}
void add(char cc)
{
++rem;
linkk = 0;
while (rem > 0)
{
if (!ind)
{
tep = s_end;
}
int& actedge_node = tree[act].alp[ss[tep] - 'a'];
if (!actedge_node)
{
actedge_node = add_new(++co, s_end);
add_link(act);
}
else
{
if (check_contain(actedge_node))
{
continue;
}
else
{
if (ss[tree[actedge_node].l + ind] != cc) // 分裂注意原树(actedge_node)必须成为子树（否则会和原先的子树失去联系）
{
int leaf1 = add_new(++co, s_end);
int leaf2 = actedge_node;
int newtree = add_new(++co, tree[actedge_node].l, tree[actedge_node].l + ind - 1);
tree[newtree].alp[cc - 'a'] = leaf1;
tree[newtree].alp[ss[tree[actedge_node].l + ind] - 'a'] = leaf2;
tree[leaf2].l += ind;
actedge_node = newtree;
add_link(actedge_node);
}
else
{
++ind; // 活跃半径只在此处增加 ，增加完就加链并结束本次增点
// if (act != root)
// {
add_link(act);
// }
break;
}
}
}
--rem;
if (act == root)
{
if (!ind)
{
break;
}
tep = s_end - rem + 1;
--ind;
}
else
{
// ind = rem - 1;
// tep = s_end - rem + 1;
if (tree[act].nex)
{
act = tree[act].nex;
}
else
{
act = root;
}
}
}
}
int dfs(int o, int cc) // 本题所需的搜索 返回1代表包含{，2代表包含|，3代表都有
{
bool bk1 = false;
bool bk2 = false;
bool stop = false;
for (int i = 0; i <= 27; ++i)
{
if (tree[o].alp[i])
{
if (tree[tree[o].alp[i]].r != maxn)
{
int contain_terminal = dfs(tree[o].alp[i], cc + check_len(tree[o].alp[i]));
if (contain_terminal == 1)
{
bk1 = true;
}
if (contain_terminal == 2)
{
bk2 = true;
}
if (contain_terminal == 3)
{
bk1 = bk2 = true;
stop = true;
}
}
else
{
if (tree[tree[o].alp[i]].l > len1)
{
bk2 = true;
}
else
{
bk1 = true;
}
}
}
}
if (stop)
{
return 3;
}
if (bk1 && bk2)
{
ans = max(ans, cc);
return 3;
}
if (bk1)
{
return 1;
}
if (bk2)
{
return 2;
}
}
int main()
{
scanf("%s%s", ss, ss2);
len1 = strlen(ss);
len2 = strlen(ss2);
ss[len1] = '{'; //ss1的结束符，防止两字符串后缀拼接
for (int i = len1 + 1; i <= len1 + len2; ++i)
{
ss[i] = ss2[i - len1 - 1];
}
ss[len1 + len2 + 1] = '|'; //ss2的结束符（也是整个合串的结束符）
for (int i = 0; i <= len1 + len2 + 1; ++i)
{
++s_end;
add(ss[i]);
}
dfs(root, 0);
printf("%d", ans);
return 0;
}
