「十二省联考2019」字符串问题 - 后缀自动机 + 拓扑排序

给定一个字符串，从中取出若干个可能相交的子串，其中一些为$A$串，另一些为$B$串。并且给定若干个从$A$串连向$B$串的单向边

规定，$A$串$A_i$到$A_j$之间有单向边当且仅当存在一个$B$串$B_k$，使得$A_i$与$B_k$相连，且$B_k$为$A_j$的前缀

$A$串的串长为其价值，求最长链

所有值不超过$2 \times 10^5$

Link

LOJ3049

Solution

这题很明显就是要优化建边过程。而前缀关系很明显可以用SAM的parent树来优化建边

具体来说，先对反串建SAM，那么parent树上一个节点子树中的所有字符串就都是这个节点的字符串的前缀了。原题中对所有前缀连边就可以只对一个点连边了

但是直接这样做是有问题的，因为SAM的一个节点会代表很多个长度不等的串。如果在连边过程中，直接从长到短往下连边的话，可能会出现从$A$向$B$连边的情况

显然，只要对每个节点包含的所有的$A/B$串排序，按len为第一关键字，len相同时$B$串在$A$串之前的顺序，再按如下方式连边即可：

for (int x = 1; x <= node_cnt; ++x)
{
	sort (vec[x].begin(), vec[x].end());

	int pre = x;
	for (int i = 0; i < vec[x].size(); ++i)
	{
		add_edge (pre, vec[x][i].id);
		if (vec[x][i].is_a == 0) pre = vec[x][i].id;
	}
	lst[x] = pre;
}

Code

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;

char S[MAXN + 5];
int NA, NB, M;
int node_cnt = 1;

namespace SAM
{
	const int MAXN = ::MAXN * 2;

	int O[MAXN + 5];

	struct info
	{
		int ch[26], fa, maxlen;
	} node[MAXN + 5];

	int lst = 1;

	inline int new_node (int pre)
	{
		int o = ++node_cnt;
		node[o].maxlen = node[pre].maxlen + 1;
		return o;
	}

	inline int extend (int c)
	{
		int o = new_node (lst), pre = lst; lst = o;

		for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = o; 

		if (!pre) node[o].fa = 1;
		else
		{
			int x = node[pre].ch[c];
			if (node[x].maxlen == node[pre].maxlen + 1) node[o].fa = x;
			else
			{
				int y = ++node_cnt; node[y] = node[x];
				node[y].maxlen = node[pre].maxlen + 1;
				node[x].fa = node[o].fa = y;
				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
			}
		}

		return o;
	}

	const int MAX_LOG = log2(MAXN);
	
	int anc[MAX_LOG + 1][MAXN + 5];

	inline void build ()
	{
		for (int i = 1; i <= node_cnt; ++i) anc[0][i] = node[i].fa;

		for (int i = 1; (1 << i) <= node_cnt; ++i)
			for (int j = 1; j <= node_cnt; ++j)
				anc[i][j] = anc[i - 1][anc[i - 1][j]];
	}

	inline int get_anc (int x, int len)
	{
		for (int i = MAX_LOG; i >= 0; --i) if (node[anc[i][x]].maxlen >= len) x = anc[i][x];
		return x;
	}

	inline void init () 
	{ 
		lst = 1; 
		for (int i = 0; i <= min (MAXN, node_cnt); ++i)
		{
			node[i].fa = node[i].maxlen = 0;
			for (int j = 0; j < 26; ++j) node[i].ch[j] = 0;
		}
	}
}

using SAM :: O;

namespace GRA
{
	const int MAXN = ::MAXN * 4;

	vector <int> G[MAXN + 5];
	int deg[MAXN + 5], Val[MAXN + 5];
	LL Dis[MAXN + 5];

	struct point
	{
		int id, len, is_a;

		point (int _id = 0, int _len = 0, int _is_a = 0) { id = _id, len = _len, is_a = _is_a; }

		inline bool operator < (const point &rhs) const { return len == rhs.len ? is_a < rhs.is_a : len < rhs.len; }
	};

	vector <point> vec[MAXN + 5];

	inline void add_edge (int x, int y) { G[x].pb (y), ++deg[y]; }

	int lst[MAXN + 5];

	inline void build_edge ()
	{
		for (int x = 1; x <= node_cnt; ++x)
		{
			sort (vec[x].begin(), vec[x].end());

			int pre = x;
			for (int i = 0; i < vec[x].size(); ++i)
			{
				add_edge (pre, vec[x][i].id);
				if (vec[x][i].is_a == 0) pre = vec[x][i].id;
			}
			lst[x] = pre;
		}

		for (int i = 1; i <= min (SAM :: MAXN, node_cnt); ++i) if (SAM :: node[i].fa) add_edge (lst[SAM :: node[i].fa], i);
	}

	inline void top_sort ()
	{
		static queue <int> Q;

		while (!Q.empty()) Q.pop();
		for (int i = 1; i <= node_cnt; ++i) if (!deg[i]) Q.push (i), Dis[i] = Val[i];

		int cnt = 0;
		LL ans = 0;
		while (!Q.empty())
		{
			int x = Q.front(); Q.pop(); ++cnt;
			Chkmax (ans, Dis[x]);

			for (int i = 0; i < G[x].size(); ++i)
			{
				int y = G[x][i];
				Chkmax (Dis[y], Dis[x] + Val[y]);
				if (!(--deg[y])) Q.push (y);
			}
		}

		if (cnt != node_cnt) puts("-1");
		else printf("%lld\n", ans);
	}

	inline void init ()
	{
		for (int i = 0; i <= node_cnt; ++i)
		{
			lst[i] = deg[i] = Val[i] = Dis[i] = 0;
			vec[i].clear(), G[i].clear();
		}
	}
}

inline void Solve ()
{
	GRA :: build_edge ();
	GRA :: top_sort ();
}

inline void Input ()
{
	scanf("%s", S + 1);
	for (int i = strlen (S + 1); i >= 1; --i) O[i] = SAM :: extend (S[i] - 'a'); 
	SAM :: build ();

	static int id[MAXN * 2 + 5];

	NA = read<int>(); 
	for (int i = 1; i <= NA; ++i)
	{
		int l = read<int>(), r = read<int>();
		int p = SAM :: get_anc (O[l], r - l + 1);
		GRA :: vec[p].pb (GRA :: point (id[i] = ++node_cnt, r - l + 1, 1));
		GRA :: Val[id[i]] = r - l + 1;
	}

	NB = read<int>(); for (int i = 1; i <= NB; ++i)
	{
		int l = read<int>(), r = read<int>();
		int p = SAM :: get_anc (O[l], r - l + 1);
		GRA :: vec[p].pb (GRA :: point (id[i + NA] = ++node_cnt, r - l + 1, 0));
	}

	M = read<int>();
	while (M--)
	{
		int x = read<int>(), y = read<int>() + NA;
		GRA :: add_edge (id[x], id[y]);
	}
}

inline void Init ()
{
	GRA :: init ();
	SAM :: init ();
	node_cnt = 1;
}

int main ()
{

#ifdef hk_cnyali
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
#endif

	int Te = read<int>();

	while (Te--)
	{
		Input ();
		Solve ();
		Init ();
	}

	return 0;
}