模板 - 字符串 - KMP算法
2024-08-22 20:57:37
要先理解前缀函数的定义,前缀函数 \(\pi(i)\) 表示字符串 \(s[0,i]\) 的同时是其最长真前缀及最长真后缀的长度,简单来说就是这个 \(s[0,i]\) 首尾最长的重叠长度(不能完全重叠)。
注意这里的字符串都是从0开始计数的。
int pi[1005];
void GetPrefixFunction(char *s, int sl) {
pi[0] = 0, pi[1] = 0;
for(int i = 1, k = 0; i < sl; ++i) {
while(k && s[i] != s[k])
k = pi[k];
pi[i + 1] = (s[i] == s[k]) ? ++k : 0;
}
}
//返回t在s中所有occurrence的首地址,s和t都是从0开始的
int ans[1005], atop;
void KMP(char *s, int sl, char *t, int tl) {
GetPrefixFunction(t, tl);
atop = 0;
for(int i = 0, k = 0; i < sl; ++i) {
while(k && s[i] != t[k])
k = pi[k];
k += (s[i] == t[k]);
if(k == tl)
ans[++atop] = i - tl + 1;
}
}
最新文章
- mysql 批量插入数据存储过程
- 使用TypeScript开发
- poj 2195 Going Home
- [Liferay6.2]Liferay入门级portlet开发示例
- angular-input
- json-lib 之jsonConfig具体应用
- pascal矩阵 分类: 数学 2015-07-31 23:01 3人阅读 评论(0) 收藏
- leetcode 109 Convert Sorted List to Binary Search Tree ----- java
- spring-boot-quartz, 依赖spring-boot-parent
- linux内核函数库文件的寻找
- Software Version
- hdu 3342 Legal or Not(拓扑排序)
- LinkedHashMap 源码详细分析(JDK1.8)
- 学好js的步骤
- [No0000196]一文读懂Java 11的ZGC为何如此高效
- JavaSE 常用类与其方法
- .net连接ORACLE数据库
- 1. Tensorflow高效流水线Pipeline
- logminer实战之生产环境写入数据字典,dg环境查询拷贝日志,测试环境进行挖掘,输出结果
- 6 Easy Steps to Learn Naive Bayes Algorithm (with code in Python)