[bzoj 3172] [Tjoi2013]单词

一篇文章由一些单词以空格分隔连接而成. 问每个单词在文章中出现多少次. (字符集=小写字母, 单词数 n ≤ 200, Σ 单词长度 ≤ 10^6) 构造后缀数组, 然后二分查找. 时间复杂度 O(L lg L).

构造 AC 自动机. 顺着 fail 边, 可以从长到短遍历某节点代表的字符串的所有后缀 (该后缀作为某个单词的前缀出现过). 每加入一个单词, 该单词所有前缀的后缀的出现次数 +1. 一个字符串是其本身的前缀, 所以, 我们可以统计每个单词的出现次数. 离线做一个单链修改, 总时间复杂度 O(|Σ| L).

后缀数组:

const int N = 1e6 + 200;

string s, t[200];

struct SuffixArray
{
	int n, sa[N], buf[2][N], * rk, * x;
	SuffixArray(): rk(buf[0]), x(buf[1]) {}
	void build(int _n)
	{
		static int c[N];
		n = _n;
		rep (i, 0, n) ++c[int(s[i])];
		rep (i, 1, 1<<(8*sizeof(char))) c[i] += c[i-1];
		per (i, n-1, 0) sa[--c[int(s[i])]] = i;
		int m = rk[sa[0]] = 0;
		rep (i, 1, n) rk[sa[i]] = m += s[sa[i-1]] != s[sa[i]];
		for (int k = 1; ++m < n; swap(x, rk), k <<= 1)
		{
			int* p = x;
			rep (i, n-k, n) *p++ = i;
			rep (i, 0, n) if (sa[i] >= k) *p++ = sa[i]-k;

			fill_n(c, m, 0);
			rep (i, 0, n) ++c[rk[i]];
			rep (i, 1, m) c[i] += c[i-1];
			per (i, n-1, 0) sa[--c[rk[x[i]]]] = x[i];

			m = x[sa[0]] = 0;
			rep (i, 1, n) x[sa[i]] = m += rk[sa[i]] != rk[sa[i-1]] || rk[sa[i]+k] != rk[sa[i-1]+k];
		}
	}
	int query(const string& t)
	{
		int l = -1, r = n, len = t.size();
		while (r-l > 1)
		{
			int m = (l+r)/2;
			if (s.substr(sa[m], len) < t) l = m;
			else r = m;
		}
		int p = r;
		l = p-1, r = n;
		while (r-l > 1)
		{
			int m = (l+r)/2;
			if (s.substr(sa[m], len) <= t) l = m;
			else r = m;
		}
		return r - p;
	}
} sa;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	rep (i, 0, n)
	{
		cin >> t[i];
		s += t[i] + ' ';
	}
	s[s.size()-1] = '\0';
	sa.build(s.size());
	rep (i, 0, n)
		cout << sa.query(t[i]) << endl;
	return 0;
}