前端之家收集整理的这篇文章主要介绍了
【数据结构】 串的模式匹配算法KMP,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
/*
==========================================================================================
串的模式匹配算法
By~fanxingzju 2014.04.27
1.Judge(T,pos,num)函数
判断String开头的num个元素组成的字符串与pos位置前的num个元素组成的字符串是否相同
2.get_next_my(T,next[])函数
根据给定的串获取KMP算法中使用的next[]数组
3.Index_KMP(S,T,pos)
串模式匹配的KMP算法
4.PrintNext(T)
打印next[]数组
5.get_next()
根据给定的串获取KMP算法中使用的next[]数组
其余的函数在“【数据结构】 串的基本操作”中已经存在
==========================================================================================
说明:
1.get_next_my()是参照【数据结构】中对KMP的介绍自己写的函数
2.get_next()是对【数据结构】中给出的函数略微修改得到的
3.由于以前版本的Index()函数不太适合使用KMP算法,这里对Index()函数进行了较大改动
4.【算法导论】中串的下标与这里略有不同,它用[0]位置来储存串的长度,这里用'\0'判断串是否结束
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
char *ch;
int length;
}HString;
bool InitString(HString &T)
{
T.ch = NULL;
T.length = 0;
return true;
}
bool StrAssign(HString &T,char *chars)
{
if (T.ch)
{
delete[] T.ch;
}
char *ctemp = chars;
T.length = 0;
while(*ctemp)
{
++T.length;
++ctemp;
}
T.ch = new char[T.length + 1];
if (!T.ch)
{
printf("StrAssign()函数执行,内存分配失败,程序即将退出\n");
system("pause");
exit(-1);
}
char *tmp = T.ch;
while(*chars)
{
*tmp++ = *chars++;
}
*tmp = '\0';
printf("StrAssign()函数执行,串T生成成功\n");
return true;
}
bool PrintString(HString T)
{
if (!T.ch)
{
printf("PrintString()函数执行,串不存在\n");
return false;
}
else
{
printf("PrintString()函数执行,串的长度为 %d ,打印结果如下:",T.length);
while(*T.ch)
{
printf("%c",*T.ch++);
}
printf("\n");
return true;
}
}
bool DestoryString(HString &Str)
{
if (Str.ch)
{
delete[] Str.ch;
}
Str.ch = NULL;
Str.length = 0;
printf("DestoryString()函数执行,串销毁成功\n");
return true;
}
// 当前正在判断的元素是HString的第pos个元素
// 判断String开头的num个元素组成的字符串与pos位置前的num个元素组成的字符串是否相同
bool Judge(HString T,int pos,int num)
{
if ((pos > T.length)||(pos < 1))
{
printf("Judge()函数执行,pos参数错误,pos = %d\n",pos);
system("pause");
exit(-2);
}
if ((num < 1)||(num > pos - 2))
{
printf("Judge()函数执行,num参数错误,num = %d\n",num);
system("pause");
exit(-2);
}
bool flag = true;
for (int i = 0; i != num; ++i)
{
if (*(T.ch + i) != *(T.ch + pos - num -1 + i))
{
flag = false;
break;
}
}
return flag;
}
bool get_next_my(HString T,int next[])
{
next[0] = 0;
for (int index = 1; index != T.length; ++index)
{
bool flag = true;
for (int len = index - 1; len != 0; --len)
{
if (Judge(T,index + 1,len))
{
next[index] = len +1;
flag = false;
break;
}
}
if (flag)
{
next[index] = 1;
}
}
return true;
}
bool get_next(HString T,int next[])
{
int i = 1,j = 0;
next[0] = 0;
while(i < T.length)
{
if ((0 == j)||(*(T.ch + i - 1) == *(T.ch + j - 1)))
{
++i;
++j;
next[i-1] = j;
}
else
{
j = next[j-1];
}
}
return true;
}
bool PrintNext(HString T)
{
int *next = new int[T.length];
if (NULL == next)
{
printf("PrintNext()函数执行,内存分配失败,程序即将退出\n");
system("pause");
exit(-1);
}
//get_next(T,next);
get_next_my(T,next);
printf("串对应对应的next[]数组如下:\n");
for(int i = 0; i != T.length; ++i)
{
if (i != T.length - 1)
{
printf("%d ",next[i]);
}
else
{
printf("%d\n",next[i]);
}
}
delete[] next;
return true;
}
//9.Index(S,pos)
int Index_KMP(HString Str,HString T,int pos)
{
if (!Str.ch||!T.ch||(0 == T.length))
{
printf("Index()函数执行,串不存在或为空串,程序即将退出\n");
system("pause");
exit(-1);
}
if ((pos < 1)||(pos > Str.length))
{
printf("Index()函数执行,pos参数错误\n");
return 0;
}
int *next = new int[T.length];
if (NULL == next)
{
printf("Index_KMP()函数执行,内存分配失败,程序即将退出\n");
system("pause");
exit(-1);
}
get_next(T,next);
int j = 0;
for (int i = pos - 1; i != Str.length - T.length + 1; )
{
if (*(Str.ch + i) == *(T.ch + j))
{
while(j != T.length)
{
if (*(Str.ch + i) != *(T.ch + j))
{
j = next[j];
if (0 == j)
{
++i;
}
else
{
--j;
}
// 将上面一段换成 j = 0;就是普通Index算法
// next[j]等于零时,直接从主串的下一个位置开始于字串比较
// next[j]非零时,将主串现在位置的元素与字串的第next[j]个元素比较
break;
}
else
{
++i;
++j;
}
}
if (j == T.length)
{
printf("Index()函数执行,主串S第%d个字符之后第一次出现与串T相同的字串的位置为:%d\n",i - T.length + 1);
delete[] next;
return (i - T.length + 1);
}
}
else
{
++i;
}
}
delete[] next;
printf("Index()函数执行,主串第%d个字符之后未找到与串T相同的字串\n",pos);
return 0;
}
int main()
{
HString T1,T2,T3;
InitString(T1);
InitString(T2);
InitString(T3);
char *tmp1 = "abaabcac";
char *tmp2 = "aaaac";
char *tmp3 = "abc";
StrAssign(T1,tmp1);
StrAssign(T2,tmp2);
StrAssign(T3,tmp3);
PrintString(T1);
PrintNext(T1);
PrintString(T2);
PrintNext(T2);
PrintString(T3);
Index_KMP(T1,T3,2);
DestoryString(T1);
DestoryString(T2);
DestoryString(T3);
system("pause");
return 0;
}