《kmp字符串模式匹配算法.doc》由会员分享，可在线阅读，更多相关《kmp字符串模式匹配算法.doc（13页珍藏版）》请在金锄头文库上搜索。
1、Kmp中查找一个字符串中是否包含另外一个字符串#include 2 #include 3 void makeNext(const char P,int next) 4 5 int q,k; 6 int m = strlen(P); 7 next0 = 0; 8 for (q = 1,k = 0; q 0 & Pq != Pk)11 k = nextk-1;12 if (Pq = Pk)13 14 k+;15 16 nextq = k;17 18 19 20 int kmp(const char T,const char P,int next)21 22 int n,m;23 int i,q;2
2、4 n = strlen(T);25 m = strlen(P);26 makeNext(P,next);27 for (i = 0,q = 0; i 0 & Pq != Ti)30 q = nextq-1;31 if (Pq = Ti)32 33 q+;34 35 if (q = m)36 37 printf(Pattern occurs with shift:%dn,(i-m+1);38 39 40 41 42 int main()43 44 int i;45 int next20=0;46 char T = ababxbababcadfdsss;47 char P = abcdabd;4
3、8 printf(%sn,T);49 printf(%sn,P );50 / makeNext(P,next);51 kmp(T,P,next);52 for (i = 0; i 0），即P0Pk-1；2. 此时比较第k项Pk与Pq,如图1所示3. 如果PK等于Pq，那么很简单跳出while循环;4. 关键！关键有木有！关键如果不等呢？那么我们应该利用已经得到的next0nextk-1来求P0Pk-1这个子串中最大相同前后缀，可能有同学要问了为什么要求P0Pk-1的最大相同前后缀呢？是啊！为什么呢？原因在于Pk已经和Pq失配了，而且Pq-k Pq-1又与P0 Pk-1相同，看来P0Pk-1这么
4、长的子串是用不了了，那么我要找个同样也是P0打头、Pk-1结尾的子串即P0Pj-1(j=nextk-1)，看看它的下一项Pj是否能和Pq匹配。如图2所示 最大子序列最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如5,-3,4,2的最大子序列就是 5,-3,4,2，它的和是8,达到最大；而 5,-6,4,2的最大子序列是4,2，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。代码如下：#includeusing namespace st
5、d;int MaxSubSeq(const int *arr,int len,int *start,int *end) int max=0; /记录目前找到的最大子序列的和 int sum=0; /记录当前子序列的和 int begin=0,finish=0; /记录当前子序列的起始下标 *start=begin;*end=finish; /记录最长子序列的起始下标 for(int i=0;imax) max=sum; *end=finish; *start=begin; if(sum=0) sum=0; begin=i+1; return max;int main() int arr6=5,
6、-3,-2,12,9,-1; int start,end; int max=MaxSubSeq(arr,6,&start,&end); coutThe MaxSubSeq is from position startto position end.endl; coutSum of MaSubSeq: maxendl; return 0;最长公共子串（LCS）找 两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结 果。这个二维矩阵怎么构造呢？直接举个例子吧：bab和caba(当然我们现在一眼就可以看出来
7、最长公共子串是ba或ab) babc000a010b101a010我们看矩阵的斜对角线最长的那个就能找出最长公共子串。不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。 babc000a010b102a020这样矩阵中的最大元素就是 最长公共子串的长度。在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。代码如下：#include#include#includeusing namespace std;/str1为横向，str2这纵向const string LCS(c
8、onst string& str1,const string& str2) int xlen=str1.size(); /横向长度 vector tmp(xlen); /保存矩阵的上一行 vector arr(tmp); /当前行 int ylen=str2.size(); /纵向长度 int maxele=0; /矩阵元素中的最大值 int pos=0; /矩阵元素最大值出现在第几列 for(int i=0;iylen;i+) string s=str2.substr(i,1); arr.assign(xlen,0); /数组清0 for(int j=0;jmaxele) maxele=ar
9、rj; pos=j; / / vector:iterator iter=arr.begin();/ while(iter!=arr.end()/ cout*iter+;/ coutendl;/ tmp.assign(arr.begin(),arr.end(); string res=str1.substr(pos-maxele+1,maxele); return res;int main() string str1(324); string str2(5); string lcs=LCS(str1,str2); coutlcsendl; return 0;最长公共子序列最长公共子序列与最长公共
10、子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程：等号约定，C1是S1的最右侧字符，C2是S2的最右侧字符，S1是从S1中去除C1的部分，S2是从S2中去除C2的部分。LCS(S1,S2)等于下列3项的最大者：（1）LCS（S1，S2）（2）LCS（S1，S2）（3）LCS（S1，S2）-如果C1不等于C2； LCS（S1，S2）+C1-如果C1等于C2；边界终止条件：如果S1和S2都是空串，则结果也是空串。下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应，矩阵中每个格子里的数字应该这么填，它等于以下3项的最大值：（1）上面一个格子里的数字（2）左
