注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

KMP算法  

2012-10-03 12:03:24|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
KMP算法的基本做法是,发生匹配时,正文串扫描k不回退,直接从失配点k起,继续向右试匹配。而且,虽然模式串扫描指针 j 需要回退,但也不是必须会退到开头处。

KMP算法分为两个阶段:
1.计算失配函数表阶段
2.匹配阶段

匹配阶段:
从串头开始试匹配。在某次试匹配过程中,如果发现a[k]与p[j]失配,从失配函数表中取出f[j]的值s,让a[k]与p[s]比较,进入下一轮匹 配。但是,如果失配点发生在模式串头,就让指针k进1(k++),再从a[k]与p[0]开始比较,进入下一轮试匹配。


KMP算法之匹配函数


int index_KMP(char a[],char p[],int f[],int m,int n)
{
//a储存的是长度为m的正文串
//p储存的是长度为n的模式串
//f存储模式串p的失配函数表
int k = 0,j = 0;
while(k < m && j < n)
{
if(j == -1) //若j退到头,k右移,j = 0
{
j ++;
k ++;
continue;
}

if(a[k] == p[j]) //若相配,k和j右移
{
j ++;
k ++;
continue;
}
j = f[j]; //若失配,k不变,j回退

}
if(j < n) return -1; //匹配失败
return k - n; //匹配成功
}




失配函数表的函数


void fail_KMP(int f[],char p[],int n)
{
//p储存长度为n的模式中
//f储存模式串p的失配函数表
int k = 0,j = f[0] = -1;
while(k < n)
{
if(j == -1)
{
j ++;
k ++;
f[k] = 0;
continue;
}
if(p[k] == p[j]) //相配,求出函数值
{
j ++;
k ++;
f[k] = j;
continue;
}
j = f[j]; //不相配,k不变,j回退
}
}





#include<iostream>
using namespace std;

int index_kmp(int n[],int m[],int f[],int a,int b)
{
int k = 0,j = 0;
while(k < a && j < b)
{
if(j == -1) {j++;k++;continue;}
if(n[k] == m[j]) {j++;k++;continue;}
j = f[j];
}
if(j < b) return -1; //k < a不成立
else return k - b + 1;
}

void fail_kmp(int m[],int f[],int n)
{
int k = 0;
int j = f[0] = -1;
while(k < n)
{
if(j == -1) {j ++;k ++;f[k] = 0;continue;}
if(m[k] == m[j]) {j++;k ++;f[k] = j;continue;}
j = f[j];
}
}
int n[1000001],m[10001];
int main()
{
int N; cin>>N;
while(N -- )
{
int a,b; cin>>a>>b;
int f[10001];
for(int i = 0;i < a;i ++) scanf("%d",&n[i]);
for(int i = 0;i < b;i ++) scanf("%d",&m[i]);
fail_kmp(m,f,b);
cout<<index_kmp(n,m,f,a,b)<<endl;
}
}


/*
Sample Input
(1 <= M <= 10000, 1 <= N <= 1000000).
[-1000000, 1000000].
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1


Sample Output
6
-1*/




  评论这张
 
阅读(92)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018