后缀自动机模板 SAM
2024-08-28 01:37:49
一点疑问:
当创建nq节点时,要不要把nq的cnt标记赋值为1?
讲道理nq节点也是代表一个子串啊,不过网上的模板都没赋值。
2017.9.18 update:
把memset部分重写,改成用节点用到时再初始化,初始化所有节点可能被卡。
fa,len,cnt数组其实不用清空,因为用时都赋值了。
struct SAM
{
static const int MAXN = <<;//大小为字符串长度两倍
static const int LetterSize = ; int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];
int sum[MAXN], tp[MAXN], cnt[MAXN]; //sum,tp用于拓扑排序,tp为排序后的数组 void init( void)
{
last = tot = ;
len[] = ;
memset( ch[], , sizeof ch[]);
} void add( int x)
{
int p = last, np = last = ++tot;
len[np] = len[p] + , cnt[last] = ;
memset( ch[np], , sizeof ch[np]);
while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
if( p == )
fa[np] = ;
else
{
int q = ch[p][x];
if( len[q] == len[p] + )
fa[np] = q;
else
{
int nq = ++tot;
memcpy( ch[nq], ch[q], sizeof ch[q]);
len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq;
while( p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
}
} void toposort( void)
{
for(int i = ; i <= len[last]; i++) sum[i] = ;
for(int i = ; i <= tot; i++) sum[len[i]]++;
for(int i = ; i <= len[last]; i++) sum[i] += sum[i-];
for(int i = ; i <= tot; i++) tp[sum[len[i]]--] = i;
for(int i = tot; i; i--) cnt[fa[tp[i]]] += cnt[tp[i]];
}
} sam;
最新文章
- @Html.Partial和@Html.Action区别
- Seo标签权重
- Redis 读后小感
- 【windows环境下】RabbitMq的安装和监控插件安装
- Bootstrap 巨幕页头缩略图和警告框组件
- ubuntu中VNC的安装配置笔记
- nodejs+express +jade模板引擎 新建项目
- hadoop 关闭进程时报错no 进程 to stop
- DataTable 无法转换的错误
- nodejs这个过程POST求
- 使用poi3.9的jar输出excel
- 解决 GoogleApi 无法访问的问题
- 快速数论变换(NTT)小结
- 配置ubuntu的超管账号密码
- 2018牛客网暑期ACM多校训练营(第三场)C Shuffle Cards(可持久化平衡树/splay)
- 【译】第三篇 SQL Server安全主体和安全对象
- 二进制包安装MYSQL——
- 3、pandas的loc和iloc数据筛选
- 使用BAPI批量修改采购信息记录的税率
- 数据库事物 jdbc事物 spring事物 隔离级别:脏幻不可重复读
热门文章
- 系统管理模块_岗位管理_改进_使用ModelDroven方案_套用美工写好的页面效果_添加功能与修改功能使用同一个页面
- iOS开发之--当遇到tableView整体上移时的解决方案
- ecstore 修改后台搜索框搜索字段的排序顺序
- Visual Studio Code 配置 gulp
- eclipse 的代码着色插件 --Eclipse Color Theme
- 电力项目七--js控制文字内容过长的显示和文本字数的显示
- 实现返回top功能
- [Android Tips] 17. 查看 APK 签名信息
- Java中static关键字用法总结
- HDU 5876 大连网络赛 Sparse Graph