POJ2774 –後綴樹解法

• 2020 年 7 月 22 日
• 筆記
• 數據結構, 樹的使用

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;
}