字符串KMP算法
2024-09-05 21:50:56
讲解:http://blog.csdn.net/starstar1992/article/details/54913261
#include <bits/stdc++.h>
using namespace std;
char a[],b[];
int nxt[];
void get_nxt(int n)
{
int p=, q=-;
nxt[p]=q;
while(p<n) {
if(q==- || a[p]==a[q])
nxt[p++]=q++;
else q=nxt[q];
}
}
int KMP(int na,int nb)
{
get_nxt(na);
int p=, q=, ans=;
while(p<nb) {
if(q==- || b[p]==a[q])
p++, q++;
else q=nxt[q];
if(q==na-) ans++;
}
return ans;
}
int main()
{
scanf("%s%s",a,b);
int na=strlen(a), nb=strlen(b);
printf("%d",KMP(na,nb));/// a串在b串中出现次数 return ;
}
最新文章
- >Python下使用subprocess中文乱码的解决方案
- 深入Docker
- jquery实现章节目录效果
- sql语句执行顺序
- p++ ++p
- ios应用数据存储方式
- mysql分区(partition)
- HDU 5366 The mook jong (简单DP)
- Django 1.6 最佳实践: 如何设置django项目的设置(settings.py)和部署文件(requirements.txt)
- C#实现自定义事件,用于监视变量变化
- js阻止冒泡事件及默认操作
- SQL的数据类型
- QT实现单个EXE文件
- 在 JPA、Hibernate 和 Spring 中配置 Ehcache 缓存
- 虚拟机设置静态IP配置
- [置顶]Python开发之路
- Python 文件读取
- vue手把手教你实现走马灯商品左右轮播图
- Java采用RSA加密及解密技术的有关Maven项目的配置流程:
- HDU 6346 整数规划 (最佳完美匹配)