Description
给定主串 (S) 和若干个模式串 (T_1,T_2,...,T_n),问 (S) 的子串中有多少个不是 (T_1,T_2,...,T_n) 中任意一个串的子串。
Solution
对 (S) 建立 SAM,则一个结点对应了 (S) 的若干个子串
将 (T_i) 放上去跑时,若跑到了一个结点 (p),此时匹配的长度为 (l),则该结点以及其后缀链接上所有节点表示的长度 (le l) 的子串都被废弃
于是考虑对每个结点维护一个匹配过的最大长度 (f[i]),统计结点 (i) 的答案时,贡献为 (len[i]-max(f[i],minlen[i]))
暴力维护需要每次修改一条链,实际上我们只需要在当前匹配的位置打标记,然后沿着后缀树上传取 max 即可
(注意没有对应出边时的处理)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 210005;
const int dbg = 0;
int max(int x,signed y)
{
return max(1ll*x,1ll*y);
}
int max(signed x,int y)
{
return max(1ll*x,1ll*y);
}
int min(int x,signed y)
{
return min(1ll*x,1ll*y);
}
int min(signed x,int y)
{
return min(1ll*x,1ll*y);
}
struct SAM
{
signed len[N], ch[N][26], fa[N], ind, last;
int t[N], a[N], cnt[N], f[N];
SAM()
{
ind = last = 1;
}
void init()
{
ind = last = 1;
memset(len,0,sizeof len);
memset(ch,0,sizeof ch);
memset(fa,0,sizeof fa);
memset(t,0,sizeof t);
memset(a,0,sizeof a);
memset(cnt,0,sizeof cnt);
memset(f,0,sizeof f);
}
inline void extend(int id)
{
int cur = (++ ind), p;
len[cur] = len[last] + 1;
cnt[cur] = 1;
for (p = last; p && !ch[p][id]; p = fa[p]) ch[p][id] = cur;
if (!p) fa[cur] = 1;
else
{
int q = ch[p][id];
if (len[q] == len[p] + 1) fa[cur] = q;
else
{
int tmp = (++ ind);
len[tmp] = len[p] + 1;
for(int i=0; i<26; i++) ch[tmp][i] = ch[q][i];
fa[tmp] = fa[q];
for (; p && ch[p][id] == q; p = fa[p]) ch[p][id] = tmp;
fa[cur] = fa[q] = tmp;
}
}
last = cur;
}
void calc()
{
memset(t, 0, sizeof t);
for(int i=1; i<=ind; i++) t[len[i]]++;
for(int i=1; i<=ind; i++) t[i]+=t[i-1];
for(int i=1; i<=ind; i++) a[t[len[i]]--]=i;
for(int i=ind; i>=1; --i) cnt[fa[a[i]]]+=cnt[a[i]];
cnt[1] = 0;
}
void run(string str)
{
int p=1,l=0;
for(int i=0;i<str.length();i++)
{
int c=str[i]-'a';
if(ch[p][c])
{
p=ch[p][c];
l++;
}
else
{
while(p&&ch[p][c]==0) p=fa[p];
if(ch[p][c])
{
l=len[p];
p=ch[p][c];
l++;
}
else
{
p=1;
l=0;
}
}
f[p]=max(f[p],l);
}
}
long long solve()
{
long long ans=0;
for(int t=ind;t>=1;--t)
{
int i=a[t];
ans+=len[i]-max(f[i],len[fa[i]]);
f[fa[i]]=min(len[fa[i]],max(f[fa[i]],f[i]));
}
return ans;
}
} sam;
void solve()
{
static int id = 0;
int n;
cin>>n;
string s;
vector <string> vec;
sam.init();
cin>>s;
for(int i=0;i<s.length();i++) sam.extend(s[i]-'a');
if(dbg)
{
for(int i=0;i<s.length();i++)
{
for(int j=i;j<s.length();j++)
{
string tmp;
for(int k=i;k<=j;k++) tmp+=s[k];
vec.push_back(tmp);
}
}
}
for(int i=1;i<=n;i++)
{
cin>>s;
sam.run(s);
if(dbg)
{
for(int i=0;i<vec.size();i++)
{
auto now=vec.begin()+i;
if(s.find(*now)!=s.npos)
{
vec.erase(now);
--i;
}
}
}
}
sam.calc();
cout<<"Case "<<++id<<": "<<sam.solve()<<endl;
if(dbg)
{
for(int i=0;i<vec.size();i++)
{
int flag=0;
for(int j=i+1;j<vec.size();j++)
{
if(vec[i]==vec[j]) flag=1;
}
if(flag)
{
vec.erase(vec.begin()+i);
--i;
}
}
cout<<"ans = "<<vec.size()<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--) solve();
}
/* Hack data
5 5
ccbbcbaabcccbabcbcaaaacabbaccccacaabcbbcbaabcccbabcbcaaaacabbaccccbaabcccbabcbcaaaacabbaccccbaabcccbabcbcaaaacabbacccacacaacabcbccbaabcabbbccaabbcbbcacabcaaacacabacbccbaacbcbcaac
abab
cc
bbb
abab
cb
*/