BZOJ 3277/3473 广义后缀自动机
2024-09-04 17:34:07
说实话没啥难的.
建一棵广义后缀自动机,暴力自底向上更新即可.
时间复杂度非常玄学,但据说是可以过的.
要注意每个串中相同的子串的贡献是都要加进去的,开始因为这个被坑了好久 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;
}
最新文章
- 中文字符匹配js正则表达式
- 【转】Source Insight的Alt + W键不能使用的解决办法
- IsBackground的理解
- GCC同时使用静态库和动态库链接
- 【Java】PrettyTime
- ios----protocol, optional ,delegate
- Mysql编辑工具中使用(Navicat查询结果显示行号)
- JavaScript标准Selection操作
- -_-#【Angular】工具函数
- 企业级IM应该帮助员工提高绩效,避免无关的信息干扰
- Android网络通信Volley框架源代码浅析(三)
- Weblogic的集群
- 【Java基础】线程和并发机制
- [HDU1282]回文数猜想
- [图形学] Chp14 GLU曲面裁剪函数程序示例及样条表示遗留问题
- 在Jekyll博客添加评论系统:gitment篇
- HTML学习 框架
- 浅析 JavaScript 中的 函数 uncurrying 反柯里化
- Convert List<;Entity>; to Json String.
- Flask使用记录