回文树(回文自动机) - URAL 1960 Palindromes and Super Abilities
2024-08-31 03:06:51
Palindromes and Super Abilities
Problem's Link: http://acm.timus.ru/problem.aspx?space=1&num=1960
Mean:
给你一个长度为n的字符串S，输出S的各个前缀中回文串的数量。
analyse:
回文树(回文自动机)的模板题。
由于回文自动机中的p是一个计数器，也相当于一个指针，记录的是当前插入字符C后回文树中有多少个节点。
那么我们只需要一路插，一路输出p-2就行。
p-2是因为一开始回文树中就有两个节点。这是两个根节点，分别是长度为偶数和奇数的回文串的根节点。
Time complexity: O(N)
Source code:
;
;
; ;
;
;
;
) ;
) ;
;
n ;
S ; ;
) ; ;
; ; );
;s);
;
}
/*
;
; ;
;
;
;
) ;
) ;
;
n ;
S ; ;
) ; ;
; ; );
;s);
;
}
/*
*/
代码2：
;
;
;
)
;
;
; ;
; ;
; ;
; );
);
;
}
;
;
)
;
;
; ;
; ;
; ;
; );
);
;
}
最新文章
- javascript 学习之自定义滚动条加滚轮事件
- FusionChart 数据的传入方式
- DAO模式应用实例
- Code Review Engine Learning
- underscore源码解析
- eclipse安装tomcate插件步骤
- Android学习之-TextView的滑动效果
- UIApplication深入研究
- ubuntu 安装 JVM 与 ElasticSearch
- PHP Predefined Interfaces 预定义接口(转)
- 在 Xcode中 修改文件中自动创建的Created by和Copyright
- 【转载】solr教程，值得刚接触搜索开发人员一看
- 数据存储（三）--JSON数据处理
- java学习记录
- The Super Powers
- docker 数据卷之进阶篇
- JavaScript数据结构与算法(五) 数组基础算法
- C++——STL内存清除
- 转://oracle deadlock死锁trace file分析之一
- 如何在自定义Filter中优雅的实现静态资源放行