#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 1000000+10;
char s[maxn],t[maxn];
int next[maxn];
int m,n,k,l,i,T;
void get_next(char str[])
{
memset(next,0,sizeof(next));
next[1] = 0;
int len = strlen(str+1),k=0;
for(int i=2;i<=len;i++)
{
if(k>0&&str[i]!=str[k+1])
k = next[k];
if(str[i]==str[k+1])
k++;
next[i] = k;
}
}
int kmp(char s[],char t[])
{
get_next(s);
int lent = strlen(t+1);
int lens = strlen(s+1);
int k=0,ans=0;
for(int i=1;i<=lent;i++)
{
if(k>0&&t[i]!=s[k+1])
k = next[k];
if(t[i]==s[k+1])
k++;
if(k==lens)
{
ans++;
k = next[k];
}
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
scanf("%s",t+1);
printf("%d\n",kmp(s,t));
}
return 0;
}
分享到:
相关推荐
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
kmp 算法 模版 kmp 算法 模版
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP是来自韩国的全能播放器,现在虽然还在开发,但原作者已转投potplayer研发,此版本是原作者最后开发的版本,XP下无敌的存在。解压密码:www.nautc.com
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
子串定位KMP(加强版)!
用java写的KMP算法,这是个描述KMP算法的java类,里面包含了主函数的实例
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
数据结构中KMP算法过程的Flash演示
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
通过C/C++编程,将传统的KMP算法与改进的KMP算法进行对比,通过运行时间、匹配速度来衡量算法性能的优劣。
acm算法模板之kmp模板,对关键代码做了注释,帮助小白理解