[题解] [TJOI2013] 单词

一篇论文是由许多单词组成，但小张发现一个单词会在论文中出现很多次，问每个单词分别在论文中出现了多少次。

$1\le n \le 200$，单词总长度不超过 $10^6$

题目链接

---

思路

很容易理解的广义 SAM 做法（不会的可以戳 这里），把所有的单词建成一个广义 SAM，然后记录一下每个单词的末尾对应的 SAM 上的节点，最后统一处理一下 cnt 然后输出即可。

代码

mivik.h

// Mivik 2020.8.20
#include <mivik.h>

MI cin;

const int $s = 201;
const int $n = 1000001;
const int S = $n << 1;
const int $c = 26;

template<typename T> inline bool gmax(T& a, const T& b) { return a < b && (a = b, true); }

namespace sam {
int tar[S][$c], pre[S], len[S], cnt[S], too[$n], seq[S], n;
int lst = 1, tot = 1;
inline int node(int l) { len[++tot] = l; return tot; }
inline void extend(int c) {
	int i = lst; int &op = tar[i][c]? lst: pre[lst = node(len[i] + 1)];
	while (!tar[i][c]) { tar[i][c] = lst; if (!(i = pre[i])) return (void)(op = 1); }
	const int o = tar[i][c]; if (len[i] + 1 == len[o]) return (void)(op = o);
	const int s = node(len[i] + 1); memcpy(tar[s], tar[o], sizeof(tar[0]));
	pre[s] = pre[o]; op = pre[o] = s;
	do { tar[i][c] = s; i = pre[i]; } while (i && tar[i][c] == o);
}
inline void work() {
	for (int i = 1; i <= tot; ++i) ++too[len[i]];
	for (int i = 1; i <= n; ++i) too[i] += too[i - 1];
	for (int i = 1; i <= tot; ++i) seq[too[len[i]]--] = i;
	for (int i = tot; i > 1; --i) {
		const int x = seq[i];
		cnt[pre[x]] += cnt[x];
	}
}
} // namespace sam
int pos[$s];
int main() {
	const int n = R;
	for (int i = 1; i <= n; ++i) {
		char c = cin.read<char>();
		sam::lst = 1;
		while (c != -1 && !isspace(c)) {
			sam::extend(c - 'a');
			++sam::cnt[sam::lst];
			c = cin.get();
		}
		gmax(sam::n, sam::len[sam::lst]);
		pos[i] = sam::lst;
	}
	sam::work();
	for (int i = 1; i <= n; ++i) cout < sam::cnt[pos[i]] < endl;
}