首页 > 其他分享 >后缀自动机

后缀自动机

时间:2022-11-03 15:34:55浏览次数:48  
标签:now 后缀 clone len Next int link 自动机

后缀自动机

// Created by CAD
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
namespace sam{
int len[maxn<<1],link[maxn<<1],Next[maxn<<1][26];
int sz,last;
void init(){ //记得初始化
sz=last=0;
len[0]=0,link[0]=-1;
}
void insert(char c){ //插入字符
int now=++sz;
len[now]=len[last]+1;
int p=last;
while(~p&&!Next[p][c-'a']){
Next[p][c-'a']=now;
p=link[p];
}
if(p==-1) link[now]=0;
else{
int q=Next[p][c-'a'];
if(len[p]+1==len[q]) link[now]=q;
else{
int clone=++sz;
len[clone]=len[p]+1;
memcpy(Next[clone],Next[q],sizeof(Next[q]));
link[clone]=link[q];
while(~p&&Next[p][c-'a']==q){
Next[p][c-'a']=clone;
p=link[p];
}
link[q]=link[now]=clone;
}
}
last=now;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
sam::init();
string s;cin>>s;
for(auto i:s) sam::insert(i);

return 0;
}

CAD加油!欢迎跟我一起讨论学习算法


标签:now,后缀,clone,len,Next,int,link,自动机
From: https://blog.51cto.com/u_15860211/5820459

相关文章

  • 7zip 命令行压缩指定后缀名
    接到一个需求,就是测试同学在测试软件的指定功能时,可能需要调试版本来查看输出信息,所以我们需要使用一个批处理文件来快速生成一个debug压缩包7zip给出了很多有用的命令......
  • 计算网络掩码,与网络前后缀介绍与计算方法
     要了解网络掩码(子网掩码)得先了解什么是IP地址IP地址是IP协议提供的一种统一的地址格式,它为互联网上的每一个网络和每一台主机分配一个逻辑地址,以此来屏蔽物理地址的差......
  • 批处理删除指定后缀的旧文件并保留该后缀最新的几个文件的dos命令
    setnum=3setsuffix=logfor/f"skip=%num%tokens=*delims="%%iin('dir/b/o-d*.%suffix%')dodel/f/q"%%i"前两行是指定保留文件的个数和指定的文件后缀......
  • 蓝桥杯-着急的WYF(不同子串个数)-Suffix Array后缀数组
    前置知识:后缀数组参考链接:https://blog.csdn.net/u013371163/article/details/60469533https://www.bilibili.com/video/BV1sb411t79N?from=search&seid=13723955058308......
  • 【XSY4180】串串游走(AC自动机,期望DP,高斯消元)
    假瑞出搬的神仙题。原题CFgym103119B。先把\(T\)去重。考虑先用\(O(nm\logk)\)建出所有串的AC自动机。注意建AC自动机的时候,为了保证空间,假设当前点\(u\)没......
  • 【XSY3993】自动机(构造)
    题面自动机题解题意:让你构造一个不超过\(n+1\)个状态的自动机,使得\(1\simn\)的\(n!\)个排列中只有\(q\)个被该自动机接受。\(q=n!\)可以先特判掉。然后找......
  • 【XSY3470】Cherry(后缀数组)
    题意:给一个长度为\(n\)的串\(S\)和一个长度为\(b\)的串\(B\),有\(m\)个文本串,初始它们都是空串。需要支持\(q\)个操作,每个操作要么是给某个文本串后面接上串\(B......
  • 【XSY2499】字符串(AC自动机+树状数组)
    题面DescriptionUPD:本题字符集为全体小写字母InputOutputSampleInput51abc3abcabc0abc3aba1abababcSampleOutput22HINT题解这个“强制在......
  • P5826 【模板】子序列自动机
    题目链接P5826【模板】子序列自动机【模板】子序列自动机题目背景本题中,若\(x\)是\(y\)的子序列,则等价于存在一个单调递增序列\(z\),满足\(|z|=|x|\),\(z_{|x|}......
  • AC自动机
    \(Kmp\)与\(Trie\)的优美结合,相当于在\(Trie\)上跑\(Kmp\)。一个重要定义:\(Fail\)指针(失配指针),指向其他路径上与该字母相同的节点。当前路径的模式串的后缀与\(fail\)指针......