「雅礼集训 2017 Day1」字符串 - 后缀自动机 + 根号平衡

给出一个长度为 $n$ 的字符串 $s$ 和 $m$ 个区间 $[l_i, r_i]$, 给定$k$

$q$次 询问. 每次给定一个长度为 $k$ 的字符串 $w$ 以及一对 $L,R$, 求所有满足 $i\in[L, R]$的 $w[l_i:r_i]$ 在 $s$ 中的出现次数之和.

$n,m,k,q\le 1\times 10^5$, $\sum |w|\le 1\times 10^5$

Link

LOJ6031

Solution

因为$k$一定，且$\sum|w|$不大，考虑根号平衡

先对$s$串建SAM，设$kq = T$

• 当$k \le \sqrt m$ 时:

  因为$k$很小，所有可能的区间$[l_i, r_i]$只有$k^2$种，可以对每个询问暴力$O(k^2)$枚举子串，丢到SAM上匹配求出对应right集合大小，再乘上这个子串对应的区间在$[L, R]$中的出现次数(用vector二分实现)即可

  复杂度是$O(k^2q\log n = O(T\sqrt m\log n)$

• 当$k > \sqrt m$时:

  此时询问很少，考虑对每个询问都暴力枚举$[L, R]$中的区间，然后倍增在SAM上匹配，复杂度是单词询问$O(m \log n)$

  要想每次倍增求的话首先要对$w$预处理出以每个点为右端点时，在SAM上匹配的节点，和最大匹配长度，这部分复杂度是单次询问$O(n)$的

  总复杂度$O\big(q(n + m\log n)\big) = O(n\sqrt m + T\sqrt m\log n)$

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 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 = 1e5;
const int LIM = sqrt (MAXN);

int N, M, Q, K;
char S[MAXN + 5];

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

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

	int node_cnt = 1, lst = 1;

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

	inline void 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[y].size = 0, node[x].fa = node[o].fa = y;
				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
			}
		}
	}

	vector <int> G[MAXN + 5];

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

	inline void dfs (int x) 
	{ 
		for (int i = 1; 1 << i <= N; ++i) anc[i][x] = anc[i - 1][anc[i - 1][x]];

		for (int i = 0; i < G[x].size(); ++i) 
		{ 
			int y = G[x][i]; 
			dfs (y); 
			node[x].size += node[y].size; 
		}
	}
	
	inline void build ()
	{
		for (int i = 1; i <= N; ++i) extend (S[i] - 'a');
		for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i), anc[0][i] = node[i].fa;
		dfs (1);
	}

	inline void match (char *S, int *O, int *Len)
	{
		int o = 1, len = 0;
		for (int i = 1; i <= K; ++i)
		{
			int c = S[i] - 'a';
			while (o > 1 && !node[o].ch[c]) o = node[o].fa, len = node[o].maxlen;

			if (node[o].ch[c]) o = node[o].ch[c], O[i] = o, ++len;
			else O[i] = 0;

			Len[i] = len;
		}
	}

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

namespace S1
{
	vector <int> vec[LIM + 5][LIM + 5];

	inline void main ()
	{
		for (int i = 1; i <= M; ++i) 
		{
			int l = read<int>() + 1, r = read<int>() + 1;
			vec[l][r].pb (i);
		}

		while (Q--)
		{
			static char S[LIM + 5];
			scanf("%s", S + 1);
			int l = read<int>() + 1, r = read<int>() + 1;
			LL ans = 0;
			for (int i = 1; i <= K; ++i)
				for (int j = i, o = 1; j <= K; ++j)
				{
					o = SAM :: node[o].ch[S[j] - 'a'];
					if (!o) break;
					int x = lower_bound (vec[i][j].begin(), vec[i][j].end(), l) - vec[i][j].begin();
					int y = upper_bound (vec[i][j].begin(), vec[i][j].end(), r) - vec[i][j].begin() - 1;
					ans += (LL) SAM :: node[o].size * max (0, y - x + 1);
				}
			printf("%lld\n", ans);
		}
	}
}

namespace S2
{
	int L[MAXN + 5], R[MAXN + 5];

	inline void main ()
	{
		for (int i = 1; i <= M; ++i) L[i] = read<int>() + 1, R[i] = read<int>() + 1;
		while (Q--)
		{
			static char S[MAXN + 5];
			scanf("%s", S + 1);
			int x = read<int>() + 1, y = read<int>() + 1;

			static int O[MAXN + 5], Len[MAXN + 5];
			SAM :: match (S, O, Len);
			
//			for (int i = 1; i <= K; ++i) cout << O[i] << ' ' ; puts("");

			LL ans = 0;
			for (int i = x; i <= y; ++i)
			{
				int l = L[i], r = R[i];
				if (r - l + 1 > Len[r]) continue;
				int o = SAM :: get_anc (O[r], r - l + 1);
//				cout << l << ' ' << r << ' ' << o << ' ' << SAM :: node[o].maxlen << endl;
				ans += SAM :: node[o].size;
			}

			printf("%lld\n", ans);
		}
	}
}

inline void Solve ()
{
	SAM :: build ();
	if (K <= LIM) S1 :: main ();
	else S2 :: main ();
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), Q = read<int>(), K = read<int>();
	scanf("%s", S + 1);
}

int main ()
{

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

	Input ();
	Solve ();

	return 0;
}