C语言实现字符串匹配KMP算法
字符串匹配是计算机的基本任务之一。
举例来说,有一个字符串"BBCABCDABABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?
下面的的KMP算法的解释步骤
1.
首先,字符串"BBCABCDABABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。
2.
因为B与A不匹配,搜索词再往后移。
3.
就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。
4.
接着比较字符串和搜索词的下一个字符,还是相同。
5.
直到字符串有一个字符,与搜索词对应的字符不相同为止。
6.
这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。
7.
一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。
8.
怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(PartialMatchTable)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。
9.
已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:
移动位数=已匹配的字符数-对应的部分匹配值
因为6-2等于4,所以将搜索词向后移动4位。
10.
因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数=2-0,结果为2,于是将搜索词向后移2位。
11.
因为空格与A不匹配,继续后移一位。
12.
逐位比较,直到发现C与D不匹配。于是,移动位数=6-2,继续将搜索词向后移动4位。
13.
逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数=7-0,再将搜索词向后移动7位,这里就不再重复了。
14.
下面介绍《部分匹配表》是如何产生的。
首先,要了解两个概念:"前缀"和"后缀"。"前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
15.
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,
- "A"的前缀和后缀都为空集,共有元素的长度为0;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
- "ABC"的前缀为[A,AB],后缀为[BC,C],共有元素的长度0;
- "ABCD"的前缀为[A,AB,ABC],后缀为[BCD,CD,D],共有元素的长度为0;
- "ABCDA"的前缀为[A,AB,ABC,ABCD],后缀为[BCDA,CDA,DA,A],共有元素为"A",长度为1;
- "ABCDAB"的前缀为[A,AB,ABC,ABCD,ABCDA],后缀为[BCDAB,CDAB,DAB,AB,B],共有元素为"AB",长度为2;
- "ABCDABD"的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB],后缀为[BCDABD,CDABD,DABD,ABD,BD,D],共有元素的长度为0。
16.
"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。
接下来,就是我自己对KMP算法的实现了。
这个算法的实现主要包括了三个方面:
1)求得我们用来搜索字符串的部分匹配值表
2)实现待搜索字符串在搜索过程中的指针的移动问题
3)如何定位我们搜索到的结果
接下来我就贴上我实现的代码
/*
*用KMP算法实现字符串匹配搜索方法
*该程序实现的功能是搜索本目录下的所有文件的内容是否与给定的
*字符串匹配,如果匹配,则输出文件名:包含该字符串的行
*待搜索的目标串搜索指针移动位数=已匹配的字符数-对应部分匹配值
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#defineKEYWORD_MAX_LENGTH100 //设定搜索串的最大长度
intkmp_table[KEYWORD_MAX_LENGTH]; //为搜索串建立kmp表
charprefix_stack[KEYWORD_MAX_LENGTH];//前缀表达式栈
charsuffix_stack[KEYWORD_MAX_LENGTH];//后缀表达式栈
intkeyword_length=0; //搜索串的长度
intrecord_position[KEYWORD_MAX_LENGTH];//记录与关键字串匹配源串中的位置
/*
*GetMatchValue:获得字符串src的部分匹配值
*/
intGetMatchValue(char*src)
{
intvalue=0;
intsrc_len=strlen(src);
char*begin=src; //初始化指向字符串第一个字符
char*end=src+(src_len-1); //初始化指向字符串最后一个字符
inti=0;
for(i=0;i<(src_len-1);i++)
{
prefix_stack[i]=*begin;
suffix_stack[i]=*end;
begin++;
end--;
}
char*p=prefix_stack;
char*q=suffix_stack+(src_len-2); //指向栈中最后一个元素
intflag=0; //用一个标志位来确定后缀栈中到最后一个元素都与前缀栈中的符号匹配
while(q>=suffix_stack)
{
if(*p==*q)
{
value++;
p++;
flag=1;
}
else{
flag=0;
}
q--;
}
if(flag==0)value=0;
returnvalue;
}
/*
*创建搜索字符串的KMP表
*/
intCreate_KMP_Table(char*str,int*table)
{
inti;
char*dst;
keyword_length=strlen(str);
for(i=0;i<keyword_length;i++)
{
if(i==0){
table[i]=0; //第一个字符无前缀和后缀,所以为0
}
else{
dst=(char*)malloc((i+2));
if(dst==NULL)
{
printf("mallocspaceerror!\n");
returnEXIT_FAILURE;
}
strncpy(dst,str,(i+1)); //匹配str的前(i+1)个字符
dst[i+1]="\0"; //注意字符串要以"/0"结尾
table[i]=GetMatchValue(dst);
free((void*)dst);
}
}
returnEXIT_SUCCESS;
}
//打印搜索字符串对应的KMP表
voidTable_Print(char*str,int*table)
{
inti;
charc=*str;
while(c!="\0")
{
printf("%-4c",c); //左对齐输出搜索字符串中的字符
c=*++str;
}
printf("\n");
for(i=0;i<keyword_length;i++)
{
printf("%-4d",table[i]);//左对齐输出每个字符对应的部分匹配值
}
printf("\n");
}
//在目标串dst_str中搜索关键子串search_str,打印出关键字串的位置信息,返回与关键字串匹配的数目
intSearch_Keyword(char*dst_str,char*search_str)
{
char*p=dst_str;
char*q=search_str;
char*temp;
//创建关键字串的KMP表
Create_KMP_Table(search_str,kmp_table);
intcount=0; //记录现在已经匹配的数目
intk=0; //记录与关键字串匹配的字串的数目
intmove=0; //当字符串不匹配时,搜索指针移动的位数
while(*p!="\0") //直到搜索到目标串的最后一个字符为止
{
temp=p;
while(*q!="\0")
{
if(*q==*temp)
{
count++;
temp++;
q++;
}
elsebreak;
}
if(count==0)
p++;
else{
if(count==keyword_length)
{
record_position[k++]=(temp-dst_str)-(keyword_length);
}
move=count-kmp_table[count-1];
p+=move;
}
count=0;
q=search_str;
}
returnk;
}
intmain(intargc,char**argv)
{
char*search_str=argv[1];
//chardst_str[]="hellowoshijpfwoshijpfwoshijwoshijpwoshijpf";
chardst_str[]="BBCABCDABABCDABCDABDE";
printf("Pleaseinputserachstringanddst_string\n");
if(search_str==NULL)
{
printf("Pleaseinputsearchstring\n");
returnEXIT_FAILURE;
}
if(dst_str==NULL)
{
printf("Pleaseinputdst_string\n");
returnEXIT_FAILURE;
}
intresult=Search_Keyword(dst_str,search_str); //放回搜索到的结果的数目
Table_Print(search_str,kmp_table);
printf("%s\n",dst_str); //输出待搜索的目标串
if(result==0)
{
printf("Sorry!Don"tfindthestring%s\n",search_str);
returnEXIT_SUCCESS;
}
else{
inti,j,num;
intbefore=0;
for(i=0;i<result;i++)
{
num=record_position[i]-before; //打印搜索串在目标串中的位置
before=record_position[i]+1;
for(j=1;j<=num;j++)
printf("");
printf("*");
}
printf("\n");
}
returnEXIT_SUCCESS;
}
测试的结果:
相关文章
- 银行家算法 C语言实现 带注释
- 操作系统linux:银行家算法(C语言实现)
- 操作系统银行家算法C语言代码实现「建议收藏」
- 八大排序算法(C语言实现)
- 用C语言实现快速排序算法「建议收藏」
- C语言背包问题的算法(附完整源码)
- C语言模拟银行家算法
- C语言的运算符及优先级[通俗易懂]
- 蓝桥杯 算法提高 数的划分(图解DFS +DP)------------C语言—菜鸟级
- 蓝桥杯 算法训练 3000米排名预测---------C语言—菜鸟级
- 【安全算法之SHA384】SHA384摘要运算的C语言源码实现
- 【安全算法之DES】DES算法(支持ECB/CBC模式)的C语言源码实现
- C语言位操作
- 带头双向循环链表增删查改实现(C语言)
- [C语言] 数据结构-衡量算法的标准详解编程语言
- C语言除法算法和取模运算的实现(多种算法,多种思路)
- C语言下的Linux程序开发之旅(clinux程序设计)
- Linux C语言实现图像处理(linuxc图像处理)
- 使用C语言和MySQL快速抓取实例的下载方法(c mysql 实例下载)
- 库C语言Oracle带来的通用类库之旅(c oracle通用类)
- 最小生成树算法C语言代码实例
- 纯C语言:折半查找源码分享
- C语言实现的排列组合问题的通用算法、解决方法
- C语言kmp算法简单示例和实现原理探究