KMP
算法学习总结
KMP
算法看似简单,其实想要完全理解还是有困难的。
KMP
其实可以搜索过程可以看成是一个自动机,分为
2
部分,第一部分自动机的构造
(
对应一般的说法就是失效函数,转移函数,
overlap
函数
)
,第二部分在自动机上搜索过程。
举个例子:
目标串味
T = acabaabaabcacaabc;
模式串
P=abaabcac
;
第一步:根据模式串构造自动机
向前的箭头表示搜索前进的方向。向后的箭头表示不匹配的回溯,即失效函数,或者状态变迁函数。例如:
f(j=1)
= 0;
f(j=2) = 0;
f(j=3) = 1;
f(j=4)
= 1;
f(j=5) = 2;
f(j=6) = 0;
f(j=7) = 1;
假如已经构造出该自动机,那么匹配算法用伪代码描述如下:
KMP-Search
:
int j = 0;
//
指示当前自动机所在状态
int i;
//
指示目标串匹配过程中的位置
int n;
//
目标串的长度
int m;
//
模式串的长度
for(i =0; i < n; i++) {
//
对目标串进行匹配
for(;;) {
if( T[i] == pattern[j] ) {
j++;
if ( j == m) {
found a match
;
//
找到一个匹配
j = overlap(j);
//
再找下一个匹配
}
break;
}
else if( j == 0 )
break;
//
如果没有与
T[i]
匹配,直接
i+1
else j =
overlap(j);
//
匹配了一部分出错的,根据箭头的指向回溯
}
}
接下里,就是对失效函数的构造,
KMP-Table
overlap(Pattern pattern)
{
初始化
overlap
用来存放失效函数的值
;
overlap [0] = -1; overlap
[1] = 0;
Int j = 2;
//
状态机的位置
Int cnd;
//
当前回溯的位置
While j < m
{
If( pattern[ j
-1 ] == pattern[cnd])
//
当前匹配成功
,
移到下一个位置,
overlap [j] = cnd +1
; cnd++; j++;
Else if( cnd > 0 )
cnd = overlap [cnd];
// cnd > 0
说明匹配了一部分后遇到不匹配,
//
根据箭头方向回溯,重新匹配;
Else overlap[j] = 0; j++;
// cnd = 0
说明当前不匹配
}
Return overlap
}
算法实现:
#include <iostream>
using namespace std;
/**
*KMP-Table
*input: pattern
*output : overlap[]
*/
void kmp_table(const char * P, int * overlap)
{
overlap[0] = -1;
overlap[1] = 0;
unsigned int j = 2;
int cnd = 0;
while(j < strlen(P))
{
if( P[j-1] == P[cnd])
{
overlap[j] = cnd + 1;
++j;
++cnd;
}
else if( cnd > 0)
cnd = overlap[cnd];
else
{
overlap[j] = 0;
++j;
}
}
}
/**
*KMP_Search
*input: char * Target ; char * Pattern:
*output ; the position of the Pattern in Traget;
**/
int kmp_search(const char * T, const char * P)
{
int n = strlen(T);
int m = strlen(P);
int * overlap = new int[m];
int j = 0;
kmp_table(P,overlap);
for( int k = 0; k < m; k++)
{
cout<<overlap[k]<< "" ;
}
cout<<endl;
for( int i = 0; i < n; i++)
{
for(;;)
{
if( T[i] == P[j])
{
j++;
if(j == m)
return i-m + 1 ;
break;
}
else if(j == 0) break;
else
{
j = overlap[j];
}
}
}
return -1;
}
int main()
{
char * S = "acabaabaabcacaabc";
char * W = "abaabcac";
int p = kmp_search(S,W);
cout<<"p = "<< p <<endl;
}
分享到:
相关推荐
自动机理论,KMP算法等自动机理论,KMP算法等
kmp算法
这是我上实验课时候做的KMP算法,基本实现了串的一些基本功能
串匹配算法 1 第一章 引言 2 第一节 2 第二节 2 第二章 精确串匹配算法 3 引论 精确串匹配算法的分类 3 ...5.kmp算法 47 A 6 自动机算法 47 A 7 bom 算法 48 A 8 shift-or 算法 50 A 9 BNDM算法 51 A 10 哈希法 51
基于单模式串和 Trie 树实现的敏感词过滤我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,前面四种算法都是单模式串
后缀自动机: , , , , , , 最低共同祖先: , , , 计数反转: , , , Euclid 的扩展算法: 后缀树: , , , , , , 动态规划:来自 clrs(essential), , , , , , , , 的章节 基本数据结构: , , , 图表: , , 最小生成树...
基本字符串全家桶(Hash,KMP,Trie,AC自动机)
AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC...
经典的KMP算法,AC自动机模型,二维kfa算法
树状数组 经典算法题每日演练——第九题 优先队列 经典算法题每日演练——第八题 AC自动机 经典算法题每日演练——第七题 KMP算法 经典算法题每日演练——第六题 协同推荐SlopeOne 算法 经典算法题每日演练——第五...
咱们从暴力匹配算法讲起,随后阐述KMP的流程 步骤、next 数组的简单求解 递推原理 代码求解,接着基于next 数组匹配,谈到有限状态自动机,next 数组的优化,KMP的时间复杂度分析,最后简要介绍两个KMP的扩展算法
KMP算法 多模式匹配算法(未完成) 字典树-Trie树; 有限自动机 树 前序,中序,后序,层序遍历; 倾斜二叉树; 算法 贪心 分治 回溯 动态规划 采取解决“最优”问题。一个问题经历多个决策,每个决策对应一个决策...
玩ACM的可以下载去看看,相信对你会有帮助的。 hash KMP 字典树 AC自动机 后缀数组 很全的字符串处理算法
当前计划后续版本更新内容:KMP、AC自动机、红黑树、AVL、SBT、Treap、块状数组、Splay、普通二叉查找树、深度搜索框架、广度搜索框架、图论相关(方向:有向图、无向图;类型:邻接表式、邻接矩阵式;包含算法:...
多种字符串匹配算法介绍与性能分析,包括kmp、ac自动机等算法。
leetcode怎么搜索好友 数据结构与算法之美 引言 : ...自动机 算法思想 贪心算法 高级篇 实战篇 推荐专栏 专栏导航 问题清单 array(数组) 算法题目 Two Sum(两数之和) LeetCode 1 题目 给定一个
AC自动机,Dijkstra,Floyd,GCD,KMP,KMP扩展,Kruskal,LCM,LCS,LIS,Prim,SPFA,埃氏筛,背包,并查集,多边形面积,二分搜索,高精度加法,高精度阶乘,级角排序,进制转换,快速幂,判断线段相交,求三角形...
基于多串匹配的有限状态自动机 未分类 归并排序 星期几的计算 N皇后构造法 几个常用的位操作 最大最小定理总结 0/1分数规划总结 (by yxysdcl 2008/11/19) 代码目录结构: 目录: 动态规划 钉子和小球 Hash+...
模式匹配算法包括AC自动解 多模式匹配算法和KMP单模式匹配算法详解
kmp算法 BF算法 AC自动机 数组和广义表 矩阵 特殊矩阵(对称矩阵,三角矩阵,对角矩阵) 稀疏矩阵(转置,十字链表) 广义表 树 二叉树 线索二叉树 赫夫曼树 图 遍历 广度优先BFS 深度优先DFS 最小生成树 Prim(普里姆)算法 ...