首页 技术 正文
技术 2022年11月23日
0 收藏 554 点赞 3,973 浏览 1621 个字

说实话没啥难的.

建一棵广义后缀自动机,暴力自底向上更新即可.

时间复杂度非常玄学,但据说是可以过的.

要注意每个串中相同的子串的贡献是都要加进去的,开始因为这个被坑了好久 QAQ

Code:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 300000
#define N 30
using namespace std;
int m,k,n,length[maxn];
char str[maxn];
string s[maxn];
struct SAM{
int last,tot;
int ch[maxn][N], f[maxn],cnt[maxn],len[maxn],C[maxn],rk[maxn],mk[maxn];
long long sumv[maxn];
void init() { last = tot = 1; }
void ins(int c){
int p=last,np,nq;
if(ch[p][c]){
int q=ch[p][c];
if(len[q]==len[p]+1) last=q;
else
{
nq=++tot,last=nq;
f[nq]=f[q],f[q]=nq,len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
while(p&&ch[p][c]==q)ch[p][c]=nq,p=f[p];
}
}
else {
np=++tot,last=np,len[np]=len[p]+1;
while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];
if(!p) f[np]=1;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) f[np]=q;
else
{
nq=++tot;
f[nq]=f[q],f[q]=f[np]=nq,len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];
}
} }
}
void Solve(){
for(int i = 1;i <= m; ++i) {
int p = 1,c,u;
for(int j = 0;j < length[i]; ++j) {
c = s[i][j] - 'a'; p = ch[p][c]; u = p;
while(u && mk[u] != i) ++cnt[u],mk[u] = i,u = f[u];
}
}
for(int i = 1;i <= tot; ++i) C[len[i]]++;
for(int i = 1;i <= tot; ++i) C[i] += C[i - 1];
for(int i = 1;i <= tot; ++i) rk[C[len[i]]--] = i;
for(int i = 1;i <= tot; ++i)
{
int t = rk[i];
sumv[t] = cnt[t] >= k ? sumv[f[t]] + (len[t] - len[f[t]]) : sumv[f[t]];
}
for(int i = 1;i <= m; ++i)
{
int p = 1;
long long ans = 0;
for(int j = 0;j < length[i]; ++j) {
p = ch[p][s[i][j]-'a'];
ans += sumv[p];
}
printf("%lld ",ans);
}
}
}T;
int main() {
//setIO("input");
scanf("%d%d",&m,&k),T.init();
for(int i = 1;i <= m; ++i) {
T.last = 1;
scanf("%s",str),s[i] = string(str),length[i] = strlen(str);
for(int j = 0;j < length[i]; ++j) T.ins(s[i][j] - 'a');
}
T.Solve();
return 0;
}

  

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141689.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,140
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,476
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:567 阅读:5,290
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,162
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,335
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,874