C++ 中KMP字符串匹配算法

核心提示： Name : KMP.C// Author : ruochenchen// Created on : 2012-11-01// Copyright : Your copyright notice// Compiler : VS2010// Language : C/C++/

 //============================================================================
// Name : KMP.C
// Author : ruochenchen
// Created on : 2012-11-01
// Copyright : Your copyright notice
// Compiler : VS2010
// Language : C/C++
// Description : KMP字符串匹配算法
//============================================================================
//-----------串的结构采用《数据结构》吴伟民版对于串定长顺序的描述

//-----------串的定长顺序储存结构-------------------
#define MAXSTRLEN 255 //最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度
int next[20];
//-----------串的定长顺序储存结构-------------------

//-----------基本操作------------------
int StrAssign(SString S,char *chars);
//初始条件：
//操作结果：生成一个其值等于串常量chars的串S
int StrLength(SString S);
//初始条件：串S存在
//操作结果：返回S的元素个数。
int StrAssign(SString S,char *chars)
{
int i=0,j=1;

while(chars[i]!='\0' && j<=MAXSTRLEN)
{
S[j]=chars[i];
j++;
i++;
}
if(chars[i]!='\0')
{
return -1;
}
S[j]='\0';
//S[0]=StrLength(S);
}

int StrLength(SString S)
{
int i=1,count=0;
while(S[i]!='\0')
{
count++;
i++;
}
return count;
}
//-----------基本操作------------------

#include<stdio.h>
#include<string.h>
void get_next(SString T,int next[]);
void get_next(SString T,int next[])
{ //求模式串T的next函数值并存入数组next。
int i=1,j=0;
next[1]=0;
while(i<T[0])
{
if(j==0 || T[j]==T[i])
{
++i;
++j;
next[i]=j;
}
else j=next[j];
}
}
int Index_KMP(SString S,SString T,int Pos)
{
int i=Pos,j=1;
int sl,tl;
sl=StrLength(S);
tl=StrLength(T);
while (i<=sl && j<=tl)
{
if(j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j=next[j];
}
}
if(j>tl)
{
printf("匹配成功");
return i-tl;
}
else
printf("无法匹配模式");
}

//----------主函数
void main()
{
SString S,T;
char Tstr[20];
int seat;
char Str[]="TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT"; //匹配的文本序列
StrAssign(S,Str);
printf("请输入模式字符串:\n");
scanf("%s",Tstr);
StrAssign(T,Tstr);
get_next(T,next);
seat=Index_KMP(S,T,1);
printf("在第%d个位置匹配",seat)
}