c++数据结构KMP算法

#include <stdioh>

#define N 9

#define M 8

typedef struct node

{ int i,j,v;

}JD;

int fast_transpos(JD ma[],JD mb[])

{ int n,col,p,k,t;

int num[M],cpot[M];

n=ma[0]j;

t=ma[0]v;

mb[0]i=n; mb[0]j=ma[0]i; mb[0]v=t;

if(t<=0)

return(0);

for(col=0;col<=n;col++)

num[col]=0;

for(p=1;p<=t;p++)

{ k=ma[p]j;

num[k]++;

}

cpot[0]=0; cpot[1]=1;

for(col=2;col<=n;col++)

cpot[col]=cpot[col-1]+num[col-1];

for(p=1;p<=t;p++)

{ col=ma[p]j;

k=cpot[col];

mb[k]i=ma[p]j;

mb[k]j=ma[p]i;

mb[k]v=ma[p]v;

cpot[col]++;

}

return(1);

}

void main()

{ JD ma[N]={{6,7,8},{1,2,12},{1,3,9},{3,1,-3},

{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}};

JD mb[N];

int i;

fast_transpos(ma,mb);

for(i=0;i<N;i++)

printf("%d,%d,%d\n",mb[i]i,mb[i]j,mb[i]v);

}

KMP算法查找串S中含串P的个数count

#include <iostream>

#include <stdlibh>

#include <vector>

using namespace std;

inline void NEXT(const string& T,vector<int>& next)

{

//按模式串生成vector,next(Tsize())

next[0]=-1;

for(int i=1;i<Tsize();i++ ){

int j=next[i-1];

while(T[i]!=T[j+1]&& j>=0 )

j=next[j] ; //递推计算

if(T[i]==T[j+1])next[i]=j+1;

else next[i]=0; //

}

}

inline string::size_typeCOUNT_KMP(const string& S,

const string& T)

{

//利用模式串T的next函数求T在主串S中的个数count的KMP算法

//其中T非空，

vector<int> next(Tsize());

NEXT(T,next);

string::size_type index,count=0;

for(index=0;index<Ssize();++index){

int pos=0;

string::size_type iter=index;

while(pos<Tsize() && iter<Ssize()){

if(S[iter]==T[pos]){

++iter;++pos;

}

else{

if(pos==0)++iter;

else pos=next[pos-1]+1;

}

}//while end

if(pos==Tsize()&&(iter-index)==Tsize())++count;

} //for end

return count;

}

int main(int argc, char argv[])

{

string S="abaabcacabaabcacabaabcacabaabcacabaabcac";

string T="ab";

string::size_type count=COUNT_KMP(S,T);

cout<<count<<endl;

system("PAUSE");

return 0;

}

#include <iostream>

#include <windowsh> //for PTSTR

#include <strsafeh> //for StringCchLength() StringCchCopy()

class StringKMP{

public:

StringKMP():m_str(NULL), m_nextval(NULL), m_size(0){}

~StringKMP(){

if(m_str != NULL){

free(m_str);

m_str = NULL;

}

if(m_nextval != NULL){

free(m_nextval);

m_nextval = NULL;

}

std::cout << "";

}

void setString(PCTSTR psz); //设置用于匹配的字符串

int indexKMP(PCTSTR pDest, int pos); //匹配失败，返回-1

private:

PTSTR m_str;

int m_size;

int m_nextval;

void get_nextval(); //求模式串的next修正值并存入数组m_nextval

};

--StringKMPcpp--

// StringKMPcpp : 定义控制台应用程序的入口点。

//

#include "stdafxh"

#include "StringKMPh"

void StringKMP::setString(PCTSTR psz){ //设置用于匹配的字符串

int size;

StringCchLength(psz, STRSAFE_MAX_CCH, (size_t )&size);

m_size = size;

if(m_str != NULL){

free(m_str);

m_str = NULL;

}

if(m_nextval != NULL){

free(m_nextval);

m_nextval = NULL;

}

m_str = (PTSTR)malloc(( size + 1 ) sizeof(TCHAR));

StringCchCopy(m_str, size + 1, psz);

m_nextval = (int )malloc( size sizeof(int));

memset(m_nextval, 0, size sizeof(int));

get_nextval();

}

int StringKMP::indexKMP(PCTSTR pDest, int pos){ //从pos位置进行查找

//匹配失败，返回-1

//利用模式串的m_nextval求模式串在pDest中第pos个字符之后的位置的KMP算法。

//其中，0 <= pos < len(pDest)

int i = pos;

int j = 0;

int size;

StringCchLength(pDest, STRSAFE_MAX_CCH, (size_t )&size);

while(i < size && j < m_size){

if(j == -1 || pDest[i] == m_str[j]){

++i;

++j;

}

else{

j = m_nextval[j];

}

}

if(j == m_size){ //匹配成功

return i - m_size - pos;

}

else //匹配失败，返回-1

return -1;

}

void StringKMP::get_nextval(){

//求模式串的next函数修正值并存入数组m_nextval

int i = 0, j = -1;

m_nextval[0] = -1;

while(i < m_size - 1){

if(j == -1 || m_str[i] == m_str[j]){

++i;

++j;

if(m_str[i] != m_str[j])

m_nextval[i] = j;

else

m_nextval[i] = m_nextval[j];

}

else{

j = m_nextval[j];

}

;

}

}

下面语句可以用来测试

/int _tmain(int argc, _TCHAR argv[])

{

StringKMP kmp;

kmpsetString(TEXT("un"));

std::cout << kmpindexKMP(TEXT("HungryAnt"), 0) << std::endl;

std::cout << kmpindexKMP(TEXT("HungryAnt"), 1) << std::endl;

std::cout << kmpindexKMP(TEXT("HungryAn"), 2) << std::endl;

kmpsetString(TEXT("Ant"));

std::cout << kmpindexKMP(TEXT("HungryAnt"), 0) << std::endl;

std::cout << kmpindexKMP(TEXT("HungryAnt"), 1) << std::endl;

std::cout << kmpindexKMP(TEXT("HungryAn"), 2) << std::endl;

return 0;

}/

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算法和实现。其他的书本上都有的。

我自己写的个程序：

测试结果如下：

113113113113113113113113113113113113113113113111311311311311311311

13113113111

at 37

贴上源代码：

#include"stdioh"

#include "conioh"

#include "stdioh"

#include "mathh"

int result;

char pat[]="13113113111";

char str[]="113113113113113113113113113113113113113113113111311311311311311311";

int next[7];

void getNext(char pat[], int next[])

{

int j = 0;

int k = -1;

next[0] = -1;

while (pat[j])

{

if ( k == -1 || pat[j] == pat[k])

{

j++;

k++;

next[j] = k;

}

else

{

k = next[k];

}

}

}

int KMP(char str1, charpat, int next)

{

int i=0,j=0;

while(str[i])

{

if(pat[j]==0)

return i-j;

if(j==0 || str[i]==pat[j])

{

++i;

++j;

}else

j=next[j];

}

if(pat[j]==0)

return i-j;

return -1;

}

int main(int argc, char argv[])

{

int i;

getNext(pat,next);

result=KMP(str,pat,next);

printf("%s\n",str);

for(i=0;i<result;i++) printf(" ");

printf("%s\n",pat);

printf("at %d\n",result);

getch();

return 0;

}

祝你好运！

以上就是关于c++数据结构KMP算法全部的内容，包括:c++数据结构KMP算法、KMP算法，输三组主串S和模式串P，输出模式串的Next(j)函数值，及该P在S中的位置的定、求KMP算法的C++代码等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！