Kmp字符串模式匹配算法.docx

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;24 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;48 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这么长的子串是用不了了，那么我要找个同样也是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 std;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,-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(当然我们现在一眼就可以看出来最长公共子串是ba或ab) babc000a010b101a010我们看矩阵的斜对角线最长的那个就能找出最长公共子串。不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。 babc000a010b102a020这样矩阵中的最大元素就是 最长公共子串的长度。在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。代码如下：#include#include#includeusing namespace std;/str1为横向，str2这纵向const string LCS(const 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=arrj; 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(21232523311324); string str2(312123223445); string lcs=LCS(str1,str2); coutlcs左上。下图给出了回溯法找出LCS的过程：最大子序列、最长公共子串、最长公共子序列奉上代码： #include#include#include#include#define LEFTUP 0#define LEFT 1#define UP 2using namespace std;int Max(int a,int b,int c,int *max) /找最大者时a的优先级别最高，c的最低.最大值保存在*max中 int res=0; /res记录来自于哪个单元格 *max=a; if(b*max) *max=b; res=1; if(c*max) *max=c; res=2; return res;/调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。string LCS(const string &str1,const string &str2) int xlen=str1.size(); /横向长度 int ylen=str2.size(); /纵向长度 if(xlen=0|ylen=0) /str1和str2中只要有一个为空，则返回空 return ; pair arrylen+1xlen+1; /构造pair二维数组，first记录数据，second记录来源 for(int i=0;i=xlen;i+) /首行清0 arr0i.first=0; for(int j=0;j=ylen;j+) /首列清0 arrj0.first=0; for(int i=1;i=ylen;i+) char s=str2.at(i-1); for(int j=1;j=xlen;j+) int leftup=arri-1j-1.first; int left=arrij-1.first; int up=arri-1j.first; if(str1.at(j-1)=s) /C1=C2 leftup+; int max; arrij.second=Max(leftup,left,up,&arrij.first);/ coutarrij.firstarrij.second ; / coutendl; /回溯找出最长公共子序列 stack st; int i=ylen,j=xlen; while(!(i=0&j=0) if(arrij.second=LEFTUP) if(arrij.first=arri-1j-1.first+1) st.push(i); -i; -j; else if(arrij.second=LEFT) -j; else if(arrij.second=UP) -i; string res