题目
给出\(n\)个字符串，问每个字符串有多少个子串满足这个子串被这\(n\)个字符串中至少\(k\)个字符串包含。（一个字符串本质相同位置不同的子串算多个）。\(1\le k\le n, \sum |s|\le 10^5\)。
分析
这是一个多串问题，考虑广义后缀自动机，建出广义后缀树。
在广义后缀树上可以方便地用启发式合并set的方法得到每个点被多少个字符串包含。接着问题就变成了如何查询答案。
直接通过set来更新答案是不现实的。
由于一个字符串本质相同位置不同算多次，所以要求的其实就是对于一个字符串的每个前缀的最长后缀被\(k\)个以上的字符串包含。这可以通过把字符串放进自动机里匹配，如果当前点的被包含数小于\(k\)就条link，跳到一个被包含数大于等于\(k\)的位置，统计这个位置的\(len\)，这是因为我们从上一个点跳过来，前缀的一个前缀被去掉，而这个点的\(len\)必定是上一个点的\(minlen-1\)，所以一定还在这个串中，即我们要统计的前缀的最长后缀包含数大于等于\(k\) 。
代码
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long giant;
const int maxn=1e5+10;
const int maxm=maxn<<1;
const int maxc=26;
string s[maxn];
set<int> st[maxm];
int n,k,cnt[maxm];
struct TREE {
vector<int> g[maxm];
void add(int x,int y) {g[x].push_back(y);}
void merge(set<int> &a,set<int> &b) {
if (a.size()<b.size()) a.swap(b);
for (int x:b) a.insert(x);
b.clear();
}
void dfs(int x) {
for (int v:g[x]) {
dfs(v);
merge(st[x],st[v]);
}
cnt[x]=st[x].size();
}
} tree;
struct SAM {
int t[maxm][maxc],len[maxm],link[maxm],tot,last;
SAM ():tot(1),last(1) {}
void reset() {last=1;}
void add(int x,int id) {
if (t[last][x]) {
int p=t[last][x];
if (len[p]==len[last]+1) {
st[last=p].insert(id);
return;
}
int q=++tot;
len[q]=len[last]+1;
memcpy(t[q],t[p],sizeof t[p]);
for (int j=last;j && t[j][x]==p;j=link[j]) t[j][x]=q;
link[q]=link[p],link[p]=q;
st[last=q].insert(id);
return;
}
int nw=++tot,i;
len[nw]=len[last]+1;
for (i=last;i && !t[i][x];i=link[i]) t[i][x]=nw;
if (i) {
int p=t[i][x];
if (len[p]==len[i]+1) link[nw]=p; else {
int q=++tot;
len[q]=len[i]+1;
memcpy(t[q],t[p],sizeof t[p]);
for (int j=i;j && t[j][x]==p;j=link[j]) t[j][x]=q;
link[q]=link[p],link[p]=link[nw]=q;
}
} else link[nw]=1;
st[last=nw].insert(id);
}
void build() {
for (int i=2;i<=tot;++i) tree.add(link[i],i);
}
giant run(string &s) {
int m=s.length(),now=1;
giant ret=0;
for (int i=0;i<m;++i) {
char c=s[i];
while (now!=1 && !t[now][c-'a']) now=link[now];
if (t[now][c-'a']) now=t[now][c-'a'];
while (now!=1 && cnt[now]<k) now=link[now];
if (cnt[now]>=k) ret+=(giant)len[now];
}
return ret;
}
} sam;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
ios::sync_with_stdio(false);
cin>>n>>k;
for (int i=1;i<=n;++i) {
string &str=s[i];
cin>>str;
int len=str.length();
sam.reset();
for (int j=0;j<len;++j) sam.add(str[j]-'a',i);
}
sam.build();
tree.dfs(1);
for (int i=1;i<=n;++i) cout<<sam.run(s[i])<<" ";
cout<<endl;
return 0;
}
转载于:https://www.cnblogs.com/owenyu/p/7144408.html
