dfa实现kmp算法

Ⅰ kmp 算法原理

朴素算法
先看看最“朴素”的算法： ///find a template in a string. #include<string.h> #include<stdio.h> int Index(char *S, char *T, int pos) { int k=pos, j=0; while(k <strlen(S) && j<strlen(T))//未超出字符串的长度 { if (S[k] == T[j]) { ++k; ++j;} //如果相同，则继续向后比较 else {k = k-j+1; j =0;} //如果不同，就回溯，重新查找 } if (j == strlen(T)) return k-strlen（T）; else return 0; }
编辑本段KMP算法
一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ(n)，只用到辅助函数π[1，m]，它是在Θ(m)时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场”有效的计算(在平摊意义上来说)变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ(q，a)时需要的信息。由于数组π只有m个元素，而δ有Θ(m∣Σ∣)个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。[1] KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。
编辑本段KMP算法的讲解
当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。
编辑本段定义
设字符串为 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字符，设ai为字符xi对应的整数。则a=m，当且仅当满足如下条件：字符串x1x2...xm equals 字符串x(i-m+1)...xi-1 xi 并且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
编辑本段举例
abcabcddes 0111234111 |----------------------默认是0 --| | |-----------------不能自己在相同位置进行字符匹配，所以这里认为没有匹配字符串，所以0+1 =1，继续从1开始匹配 ------| | |-----------前面的字符和开始位置的字符相同，所以是2,3,4 -----------| | | |-------不匹配只能取1。 希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。 程序写出来就是： void GetNext(char* T, int *next) { int k=1,j=0; next[1]=0; while( k〈 T[0] ){ if (j ==0 || T[k] == T[j]) { ++k; ++j; next[k] = j; } else j= next[j]; } } 但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下： void GetNextEx(char *T, char *next) { int k=1,j=0; next[1] = 0; while(k < T[0]) { if (j == 0 || T[k] == T[j]) { ++k; ++j; if (T[k] == T[j]) next[k] = next[j]; else next[k] = j; } else j = next[j]; } } 现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了： 相当简单： int KMP(char* S, char* T, int pos) { int k=pos, j=1; while (k){ if (S[k] == T[j]){ ++k; ++j; } else j = next[j]; } if (j>T[0]) return k-T[0]; else return 0; } 和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)
编辑本段KMP算法的伪代码
KMP-MATCHER(T，P) 1n ← length[T] 2m ←length[P] 3π ← COMPUTE-PREFIX-FUNCTION(P) 4q ← 0△Number of characters matched. 5for i ← 1 to n△Scan the text from left to right. 6do while q>0 and P[q+1]≠T[i] 7do q ← π[q]△Next character does not match. 8if P[q+1]=T[i] 9then q ← q+1△Next character matches. 10if q=m△Is all of P matched? 11then print “Pattern occurs with shift” i-m 12q ← π[q]△Look for the next match. COMPUTE-PERFIX-FUNCTION(P) 1m ← length[P] 2π[1] ← 0 3k ← 0 4for q ← 2 to m 5do while k>0 and P[k+1]≠P[q] 6do k ← π[k] 7if P[k+1]=P[q] 8then k ← k+1 9π[q] ← k 10return π[1]
编辑本段KMP算法的c++实现
//c++实现的KMP算法，所有涉及字符串，其初始下标从0开始(上述算法均是从1开始) //example: char s[100],t[100];cin>>s>>t;KMP(s,t); //获取待查询模式的next数组 int* get_next(char* T, int* next){ int i = 0, j = -1; int length = strlen(T); int *temp = next; *next = -1; while(i< length){ if(j==-1 || *(T+i)==*(T+j)){ i++; j++; //优化后的get_next方法，可以防止出现形如"aaaaab"这种模式的计算退化 if(*(T+i)!=*(T+j)) *(next+i)=j; else *(next+i)=*(next+j); } else j=*(next+j); } return temp; } //KMP算法 int KMP(char *S, char *T){ int S_Length = strlen(S); int T_Length = strlen(T); //若模式长度大于字符串，则直接返回查询失败 if( S_Length < T_Length) return 0; int i = 0, j = 0; int* next = new int[T_Length]; get_next(T, next); while(i < S_Length && j < T_Length){ if(j == -1 || *(S+i) == *(T+j)){ i++; j++; } else j=*(next+j); } if(j>=T_Length) return i-T_Length; return 0; } 在此提供一个更简明的适用于字符串的kmp实现： #include<iostream> #include<string.h> int next[100]; void getnext(char b[]) { int i=1,j=0; //i是每个位子，j是回退的位子 next[1]=0; while(i<=strlen(b)) { if(j==0||b[i-1]==b[j-1]) { i++; j++; next[i]=j; } else j=next[j]; //用上一个的 回退关系 } } int kmp(char a[],char b[]) { int i=1,j=1; //i是主串中的位子 ，j匹配串的位子 while(i<=strlen(a)&&j<=strlen(b)) { if(j==0||a[i-1]==b[j-1]) { i++; j++; } else j=next[j]; } if(j>strlen(b)) return i-strlen(b); else return 0; } int main() { char a[40],b[40]; printf("要匹配的主串：\n"); scanf("%s",a); printf("要匹配的子串：\n"); scanf("%s",b); getnext(b); printf("输出next值：\n"); for(int i=1;i<=strlen(b);i++) printf("%d ",next[i]); printf("\n"); printf("%d",kmp(a,b)); system("pause"); main(); return 0; }
编辑本段串的最大匹配算法
摘要：
给定两个串S和T，长分别m和n，本文给出了一个找出二串间最大匹配的算法。该算法可用于比较两个串S和T的相似程度，它与串的模式匹配有别。
关键词：
模式匹配 串的最大匹配 算法 Algorithm on Maximal Matching of Strings Lin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun （Computer Science Department of Yunnan Normal University Kunming 650092） ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T, it is different with the strings' pattren matching. KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm
编辑本段问题的提出
字符串的模式匹配主要用于文本处理，例如文本编辑。文本数据的存储（文本压缩）和数据检索系统。所谓字符串的模式匹配[2]，就是给定两个字符串S和T，长度分别为m和n，找出T中出现的一个或多个或所有的S，在这方面已经取得了不少进展[3][4][5][6][7][8][9][10][11]。本文从文本处理的另一个角度出发，找出两个串的最大匹配，比较其相似程度[1]。它主要应用于文本比较，特别是在计算机辅助教学中。显然前者要找S的完全匹配，而后者并无此要求。例如，若S=ABCD，T=EFABCDX，那么模式匹配的结果就是找出了T中的一个ABCD，而我们算法的结果就是S能与T的ABCD完全匹配，但是T中还有3个字符是比S多出来的，也就是说在S中有100%的字符与T中的匹配，而在T中有57%的字符与S中的匹配。若S= ABCDFE，T=AFXBECDY。则在模式匹配中S与T无匹配项，但在我们的算法中就能发现T中存在A，B，C，D，但D后不存在E，F。而且S中也存在A，B，C，D，且具有顺序性。这样就能公正地评价S，T的区别。得知其相似程度。 文章的组织如下：首先介绍基本定义和问题的描述；第三节是算法设计；最后是本文总结。
编辑本段问题的描述
设∑为任意有限集，其元称为字符，w：∑→N为∑到N的函数，称为∑的权函数（注：本文仅讨论权值恒为1的情况）。∑*为∑上的有限字符串集合，那么对任意S，T∈∑*，设S=a1a2…am，T=b1b2…bn，m>0，n>0。记<m>={1,2, …,m},<n>={1,2, …,n}，则称{(i,j)∣i∈<m>，j∈<n>，ai=bj}为S与T的匹配关系集，记作M（S，T），称M为S与T的一个（容许）匹配，若对任意（i,j）, ( i',j' )∈，① i< i'，当且仅当j< j'，② i= i'当且仅当j= j'。S与T的匹配中满足 最大者，称为S与T的最大匹配。若C(i,j)为N上的m×n矩阵，且满足： 则称矩阵C为串S与T的匹配关系阵。 于是求串S与T的最大匹配，等价于求C中的一个最大独立点集M，它满足，若ci,j，ci',j'∈M，则i< i' 当且仅当j< j'，i=i'当且仅当j=j'。我们称这样的最大独立点集为C的最大C-独立点集。 例：设∑为所有字母的集合，对任意x∈∑，w（x）≡1，设S与T分别为：S=“BOOKNEWS”，T=“NEWBOOKS”。则我们可以得到S与T两个匹配： 这里=5； 这里 =4。 显然为串S与T的最大匹配。 S与T的匹配关系阵C可表示如下： 其中带圈的部分为一最大C-独立点集。
编辑本段算法设计
我们仅就权值为一的情况进行讨论。 设S和T为任意给定串，C为的S与T匹配关系阵，那么由2的讨论知，求S与T的最大匹配问题，等价于求C的最大C-独立点集问题。因而，为了解决我们的问题，只要给出求C的最大C-独立点集的算法就可以了。 显然，为了求出C的最大C-独立点集，我们可以采用这样的方法：搜索C的所有C-独立点集，并找出它的最大者。这种方法是可行的，但并不是非常有效的。这会使问题变得很繁，复杂度很大。因此，我们先对问题进行分析。 在下面的讨论中，我们把C的任一C-独立点集={ai1,j1，…，ais,js}，记作=ai1,j1…ais,js，i1 <…< is。于是可看作阵C中以1为节点的一条路，满足：对路中的任意两节点，均有某一节点位于另一节点的右下方。称这种路为右下行路。 于是求C-独立点集等价于求阵C的右下行路。这种求右下行路的搜索可以逐行往下进行。 命题1. 若 =αai,jβ和ψ=α'ai,jσ为C的两个C-独立点集，且α为α'的加细，则存在C-独立点集'=αai,jδ，满足≥。 命题2. 若 =αai,jβ和ψ=α'ai+k,jσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。 命题3. 若 =αai,jβ和ψ=α'ai,j+kσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。 由命题1知，在搜索右下行路的过程中，如果已获得了某一C-独立点集的某一初始截段αai,j和另一C-独立点集ψ的某一初始截段α'ai,j，且有≤，则我们可以停止对ψ的进一步搜索。 由命题2知，在搜索右下行路的过程中，在某一列j存在某两个C-独立点集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，则我们可以停止对ψ的进一步搜索。 由命题3知，在搜索右下行路的过程中，在某一行i存在某两个C-独立点集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，则我们可以停止对ψ的进一步搜索。 由此可见，并不要求搜索所有C的最大C-独立点集，而可以采用比这简单得多的方法进行计算。那么按照我们上面的三个命题，来看如下实例： 首先我们得到=B（在上的节点用①表示），我们向右下方找路，可以发现，在第4列有两个1，根据命题2，我们选择上面的一个1，也就是说选择第1行的那个1，而不要第2行的那个1。同时我们也发现在第1行也有两个1，由命题3知，我们选择左边的那个1，即第4列的那个1。此时=BO。但是当我们的算法运行到第4行时，=BOOK，由于K在第3行第6列，而本行的1在第1列，在路最后一个节点K的左边，那么我们必须新建一条路ψ，因为我们并不能确定是否以后就有≥，当算法运行到第6行时，=BOOK，ψ=NEW，=4，=3，我们将S链到路上，此时我们得到最长右下行路=BOOKS，=5。这样我们就可以计算出这两个字符串的匹配程度。 在我们的算法设计过程中，用到了两个技巧。技巧之一，矩阵C不用存储，是动态建立的，节省了空间。技巧之二，本算法并不要求所有的S与T中所有的元素都相互进行比较，也并不存储所有的右下行路，节省了时间和空间。由矩阵中1的出现情况可见，本算法所需的空间和时间都远小于O（mn）
编辑本段结束语
本文给出了一个与模式匹配不同的，具有若干应用的，串的最大匹配算法，该算法已经在机器上实现，达到了预期的效果。本文仅讨论权值恒为1的情况，对于权值任意的情形不难由此得到推广。
编辑本段C语言代码(C Code)
#include<stdio.h> #include<string.h> void getnext(int next[],char s[],int l) { int i=1,j=0; next[1]=0; while(i<l) { if(j==0 || s[i]==s[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int KMP(char s1[],char s2[],int l1,int l2,int next[]) { int i,j; i=j=1; while(i<=l1 && j<=l2) { if(j==0||s1[i]==s2[j]) { i++;j++; } else j=next[j]; } if(j>l2) return(i-l2); return 0; } int main() { int next[10001],ans; char s1[10001],s2[10001],l1,l2; scanf("%s",s1+1); scanf("%s",s2+1); l1=strlen(s1+1); l2=strlen(s2+1); getnext(next,s2,l2); ans=KMP(s1,s2,l1,l2,next); if(ans!=0) printf("%d\n",ans); else printf("No!\n"); system("pause"); return 0; }
编辑本段KMP算法的pascal实现
var next:array [1 ..1000001] of longint; s,t:ansistring; procere get_next(t:ansistring); var j,k:integer; begin j:=1; k:=0; while j<length(t) do begin if (k=0) or (t[j]=t[k]) then begin inc(j); inc(k); next[j]:=k; end else k:=next[k]; end; end; function index(s:ansistring;t:ansistring):longint; var i,j:longint; begin get_next(t); index:=0; i:=1; j:=1; while (i<=length(s))and(j<=length(t)) do begin if (j=0)or(s[i]=t[j]) then begin inc(i); inc(j); end else j:=next[j]; if j>length(t) then index:=i-length(t); end; end; begin readln(s); readln(t); writeln(index(s,t)) end.
编辑本段KMP播放器
K-multimedia player的缩写
来自韩国的影音全能播放器，与Mplayer一样从linux平台移植而来的Kmplayer(简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展KMP可以支持层出不穷的新格式。强大的插件功能,直接从Winamp继承的插件功能，能够直接使用winamp的音频 ，输入，视觉效果插件，而通过独有的扩展能力，只要你喜欢，可以选择使用不同解码器对各种格式进行解码。 KMPlayer The Professional Media Player! 它支持 Winamp 2/5 的输入、常规、DSP、视觉效果、媒体库插件。无须注册表支持直接调用 Directshow 滤镜！FFdshow 的视觉特效系统~超强的 GUI 界面~安装电视卡后可以直接代替原软件直接收看电视~支持播放 DVD/VCD 以及绝大多数电脑的媒体文件（AVI 支持 Xvid/DivX/3vid/H264 OGG/OGM/MKV 容器/AC3/DTS 解码~Monkey Audio 解码~）强烈推荐！此播放器除了会将自己的配置信息写入注册表外绝对绿色~ KMplayer内置目前常见的所有解码器，包括real,QT等。 另外KMplayer安装版也是目前很少见的检查流氓软件的安装方式，如果一旦有恶意的汉化小组汉化并捆绑了流氓软件。该安装程序自动会识别，并作出提示，建议用户不要安装，虽然不是特别准确，但KMplayer的无广告及第三方插件的特点使其深受好评。 目前韩国官方已经在Kmplayer里自带了中文字库，只要用户是中文系统，软件就会自动识别，十分方便。 KMP版本: KMPlayer3.0.0.1439

Ⅱ 数据结构中的KMP算法怎样用C实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define MAX_LEN_OF_STR 30 // 字符串的最大长度
typedef struct String // 这里需要的字符串数组,存放字符串及其长度{
char str[MAX_LEN_OF_STR]; // 字符数组
int length;// 字符串的实际长度
}String, *PString;
// 得到字符串的next数组
void GetNextArray(PString pstr, int next[])
{assert(NULL != pstr); <br/>assert(NULL != next);<br/>assert(pstr->length > 0);// 第一个字符的next值是-1,因为C中的数组是从0开始的<br/>next[0] = -1;<br/>for (int i = 0, j = -1; i < pstr->length - 1; )<br/>{// i是主串的游标,j是模式串的游标// 这里的主串和模式串都是同一个字符串<br/> if (-1 == j || // 如果模式串游标已经回退到第一个字符<br/>pstr->str[i] == pstr->str[j]) // 如果匹配成功<br/> {// 两个游标都向前走一步<br/> ++i;++j;// 存放当前的next值为此时模式串的游标值<br/> next[i] = j;<br/> }else // 匹配不成功j就回退到上一个next值
{j = next[j];}}}
// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串,pos是S中的起始位置
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(PString S, PString T, int pos)
{assert(NULL != S);<br/> assert(NULL != T);<br/> assert(pos >= 0);<br/> assert(pos < S->length);<br/>if (S->length < T->length)<br/> return -1;<br/>printf("主串\t = %s\n", S->str);<br/>printf("模式串\t = %s\n", T->str);<br/>int *next = (int *)malloc(T->length * sizeof(int));// 得到模式串的next数组<br/>GetNextArray(T, next);<br/>int i, j;<br/>for (i = pos, j = 0; i < S->length && j < T->length; ){// i是主串游标,j是模式串游标<br/> if (-1 == j || // 模式串游标已经回退到第一个位置<br/> S->str[i] == T->str[j]) // 当前字符匹配成功<br/> {// 满足以上两种情况时两个游标都要向前进一步<br/> ++i;++j;}
else // 匹配不成功,模式串游标回退到当前字符的next值
{j = next[j];}}
free(next);
if (j >= T->length)
{// 匹配成功
return i - T->length;}
else{// 匹配不成功
return -1;}}

Ⅲ KMP模式匹配算法是什么

KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。

1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。

图1改进算法的模式匹配过程示意

Ⅳ 数据结构里实现KMP算法

KMP算法的C语言实现2007-12-10 23:33

基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);

char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;

int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}

int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}

void get_next(char *t,int *next)
{

int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}

}

Ⅳ KMP算法的原理及其应用

KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后再上面的算法中使用。
讲解一下：
当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。
定义如下：设字符串为 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字符，设ai为字符xi对应的整数。则a=m，当且仅当满足如下条件：字符串x1x2...xm equals 字符串x(i-m+1)...xi-1 xi 并且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
举例如下：
abcabcddes
0111234111
|----------------------默认是0
--| | |-----------------不能自己相同字符匹配，所以这里者能认为是没有所以是0+1 =1
------| | |-----------前面的字符和开始位置的字符相同，所以是2,3,4
-----------| | | |-------不匹配只能取1。
希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。
程序写出来就是：
void GetNext(char* T, int *next)
{
int k=1,j=0;
next[1]=0;
while( k〈 T[0] ){
if (j ==0 || T[k] == T[j])
{
++k;
++j;
next[k] = j;
}
else j= next[j];
}
}
但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：
void GetNextEx(char *T, char *next)
{
int i=k,j=0; next[1] = 0;
while(k < T[0])
{
if (j == 0 || T[k] == T[j])
{
++k; ++j;
if (T[k] == T[j])
next[k] = next[j];
else
next[k] = j;
}
else j = next[j];
}
}
现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了：
相当简单：
int KMP(char* S, char* T, int pos)
{
int k=pos, j=1;
while (k){
if (S[k] == T[j]){ ++k; ++j; }
else j = next[j]
}
if (j>T[0]) return k-T[0];
else return 0;
}
和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)

Ⅵ ！！编译原理DFA和NFA

DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

Ⅶ KMP算法

算法3.5——KMP算法
1. 在串S和串T中分别设比较的起始下标i和j；
2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则
2.2 将j向右滑动到next[j]位置，即j=next[j]；
2.3 如果j=0，则将i和j分别加1，准备下一趟比较；
3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；
void GetNext(char T[ ], int next[ ])
{
next[1]=0;
j=1; k=0;
while (j<T[0])
if ((k= =0)| |(T[j]= =T[k])) {
j++;
k++;
next[j]=k;
}
else k=next[k];
}

Ⅷ KMP算法详细代码

KMP.java

源代码为：

package algorithm.kmp;

/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}

Ⅸ 求kmp算法的详细解释。（最好附上能运行的程序）

t;i),那么next[i]就是所有这样的j的最大值
形象地说,就是假如第i 1个字符匹配失败之后,下一个可能匹配位置至少应该往后挪动多少

就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0

计算过程基本上抄自算法导论,假设str长度为n
k=0;//k表示当前匹配了多少位
next[1]=0;
for (i=1;in;i )
{
while (k

Ⅹ 什么是KMP算法

KMP就是串匹配算法
运用自动机原理
比如说
我们在S中找P
设P＝{ababbaaba}
我们将P对自己匹配
下面是求的过程:{依次记下匹配失败的那一位}
[2]ababbaaba
......ababbaaba[1]
[3]ababbaaba
........ababbaaba[1]
[4]ababbaaba
........ababbaaba[2]
[5]ababbaaba
........ababbaaba[3]
[6]ababbaaba
..............ababbaaba[1]
[7]ababbaaba
..............ababbaaba[2]
[8]ababbaaba
.................ababbaaba[2]
[9]ababbaaba
.................ababbaaba[3]
得到Next数组‘0,1,1,2,3,1,2,2,3’
主过程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)转[4]否则转[3]
[3]若j=0或a[i]=b[j]则【inc(i)inc(j)转[2]】否则【j:=next[j]转2】
[4]若j>m则return(i-m)否则return -1;
若返回－1表示失败，否则表示在i-m处成功
若还不懂mail:[email protected]

参考一下这里吧:

http://www.chinaaspx.com/archive/delphi/4733.htm