3277: 串 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 309 Solved: 118 [Submit][Status][Discuss] Description 字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。 Input 第一行两个整数n，k。 接下来n行每行一个字符串。 Output 输出一行n个整数，第i个整数表示第i个字符串的答案。 Sample Input 3 1 abc a ab Sample Output 6 1 3 HINT 对于100%的数据，n,k,l<=100000
算法讨论：
首先对这些串建立出广义后缀自动机，同时在建立的时候要保存当前结点都是哪些串的子串，然后建立出Parent树，
对树进行一遍DFS，把一个点的所以后代结点的颜色信息全部合并到自己身上，并用一个数组来维护当前结点有多少颜色，也就是多少个串的子串。
因为我们知道，一个点在Parent树上的父亲结点是其的最长后缀，所以如果一个点有颜色Q,那么其所有祖先结点全部有颜色Q。
然后对于每个串跑自动机，如果一个当前结点的颜色数目小于K，就沿其fail指针向上跳，跳到一个大于等于K的地方，
此时答案应该加上min(这个点的len, 当前ln + 1的最小值)。 至于这个ln是做什么的，容我再想想。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
#include <string>
using namespace std;
const int N = 100000 + 5;
const int C = 26;
typedef long long ll;
int n, cnt, k;
int head[N << 1], color[N << 1];
string s[N];
set <int> occ[N << 1];
set <int> :: iterator it;
struct State {
int pre, len, next[C];
}st[N << 1];
struct SuffixAutomaton {
int sz, last;
void Init() {
sz = last = 1;
st[sz].pre = -1; st[sz].len = 0;
sz ++;
}
void add(int c, int ccc) {
int cur = sz ++, p;
st[cur].len = st[last].len + 1;
for(p = last; p != -1 && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -1) st[cur].pre = 1;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + 1) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + 1;
for(int i = 0; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != -1 && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
occ[cur].insert(ccc);
}
}sam;
struct Edge {
int from, to, next;
}edges[N << 1];
void insert(int from, int to) {
++ cnt;
edges[cnt].from = from; edges[cnt].to = to;
edges[cnt].next = head[from]; head[from] = cnt;
}
void dfs(int u) {
for(int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
dfs(v);
if(occ[u].size() < occ[v].size())
swap(occ[u], occ[v]);
for(it = occ[v].begin(); it != occ[v].end(); ++ it)
occ[u].insert(*it);
}
color[u] = occ[u].size();
}
int main() {
//freopen("stringa.in", "r", stdin);
//freopen("stringa.out", "w", stdout);
int __size__ = 50 << 20;
char *__p__ = (char*)malloc (__size__) + __size__;
__asm__("movl %0, %%esp" :: "r"(__p__));
//ios :: sync_with_stdio(false);
cin >> n >> k;
sam.Init();
for(int i = 1; i <= n; ++ i) {
cin >> s[i];
int len = s[i].length();
for(int j = 0; j < len; ++ j) sam.add(s[i][j] - 'a', i);
sam.last = 1;
}
for(int i = 1; i < sam.sz; ++ i)
if(st[i].pre != -1) insert(st[i].pre, i);
dfs(1);
for(int i = 1; i <= n; ++ i) {
if(k > n) { cout << 0 << " "; continue; }
ll ans = 0;
int p = 1, ln = 0, len;
len = s[i].length();
for(int j = 0; j < len; ++ j) {
p = st[p].next[(int) s[i][j] - 'a'];
while(color[p] < k) p = st[p].pre;
ln = min(ln + 1, st[p].len);
ans += ln;
}
cout << ans << " ";
}
//fclose(stdin); fclose(stdout);
return 0;
}