C语言实现字符串匹配KMP算法

字符串匹配是计算机的基本任务之一。

举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

下面的的KMP算法的解释步骤

1.

首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

2.

因为B与A不匹配,搜索词再往后移。

3.

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符,还是相同。

5.

直到字符串有一个字符,与搜索词对应的字符不相同为止。

6.

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

7.

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

8.

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

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>
#define KEYWORD_MAX_LENGTH 100      //设定搜索串的最大长度
int kmp_table[KEYWORD_MAX_LENGTH];  //为搜索串建立kmp表char prefix_stack[KEYWORD_MAX_LENGTH]; //前缀表达式栈char suffix_stack[KEYWORD_MAX_LENGTH]; //后缀表达式栈int keyword_length = 0;  //搜索串的长度int record_position[KEYWORD_MAX_LENGTH]; //记录与关键字串匹配源串中的位置
/**GetMatchValue:获得字符串src的部分匹配值*/int GetMatchValue(char *src){    int value = 0;    int src_len = strlen(src);    char *begin = src;    //初始化指向字符串第一个字符    char *end = src + (src_len - 1);  //初始化指向字符串最后一个字符    int i = 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);  //指向栈中最后一个元素    int flag = 0;   //用一个标志位来确定后缀栈中到最后一个元素都与前缀栈中的符号匹配    while(q >= suffix_stack)    {        if(*p == *q)        {            value++;            p++;            flag=1;        }        else {            flag = 0;        }        q--;    }    if(flag == 0) value = 0;    return value;}
/**创建搜索字符串的KMP表*/int Create_KMP_Table(char *str,int *table){    int i;    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("malloc space error!\n");                return EXIT_FAILURE;            }            strncpy(dst,str,(i+1));   //匹配str的前(i+1)个字符            dst[i+1] = '\0';    //注意字符串要以'/0'结尾            table[i] = GetMatchValue(dst);             free((void*)dst);            }    }    return EXIT_SUCCESS;}
//打印搜索字符串对应的KMP表void Table_Print(char *str,int *table){    int i;    char c = *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,打印出关键字串的位置信息,返回与关键字串匹配的数目int Search_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);        int count = 0;  //记录现在已经匹配的数目    int k = 0;     //记录与关键字串匹配的字串的数目    int move = 0;  //当字符串不匹配时,搜索指针移动的位数    
    while(*p != '\0')   //直到搜索到目标串的最后一个字符为止    {        temp = p;        while(*q != '\0')        {            if(*q == *temp)            {                count++;                temp++;                q++;            }            else break;        }                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;    }    return k;}
int main(int argc,char **argv){    char *search_str = argv[1];    //char dst_str[] = "hello woshijpf woshijpf woshij woshijp woshijpf";    char dst_str[] = "BBC ABCDAB ABCDABCDABDE";        printf("Please input serach string and dst_string\n");    if(search_str == NULL)    {        printf("Please input search string\n");        return EXIT_FAILURE;    }
    if(dst_str == NULL)    {        printf("Please input dst_string\n");        return EXIT_FAILURE;    }        int result = Search_Keyword(dst_str,search_str);  //放回搜索到的结果的数目    Table_Print(search_str,kmp_table);    printf("%s\n",dst_str);         //输出待搜索的目标串    if(result == 0)    {        printf("Sorry!Don't find the string %s\n",search_str);        return EXIT_SUCCESS;    }    else {        int i,j,num;        int before = 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");    }        return EXIT_SUCCESS;}

  测试的结果:

  

(0)

相关推荐

  • 字符串的模式匹配详解--BF算法与KMP算法

    一.BF算法     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果. 举例说明: S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcabab

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++

  • C语言中实现KMP算法的实例讲解

    一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多: 主串指针如果不回溯的话,速度就会加快,那我们就会想: 如何让主串指针不回溯? KMP算法就是解决了这个问题,所以速度变得更快速了. 它是这样子的: 用一个数组:next[] 求得失配时的位置,然后保存下来. 要说清楚KMP算法,可以从朴素的模式匹配算法说起.  朴素的模式匹配算法比较容易理解,其实现如下 int Index(char s[], char p[], int pos) { int i, j, slen, plen; i =

  • C语言kmp算法简单示例和实现原理探究

    以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下"奥,它是做模式匹配的"这点干货.最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单). 模式匹配的经典应用:从一个字符串中找到模式字串的位置.如"abcdef"中"cde"出现在原串第三个位置.从基础看起 朴素的模式匹配算法 A:abcdefg  B:cde 首先B从A的第一位开始比较,B++==A++,如果全

  • c语言中使用BF-KMP算法实例

    直接上代码 复制代码 代码如下: #define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h> #define MAX_SIZE 255    //定义字符串的最大长度 typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度//BFint BFMatch(char *s,char *p){    int i,j;  

  • KMP算法精解及其Python版的代码示例

    KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式

  • C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • 使用C语言解决字符串匹配问题的方法

    最常想到的方法是使用KMP字符串匹配算法: #include <stdio.h> #include <stdlib.h> #include <string.h> int get_nextval(char *pattern, int next[]) { //get the next value of the pattern int i = 0, j = -1; next[0] = -1; int patlen = strlen(pattern); while ( i &l

  • 详解小白之KMP算法及python实现

    在看子串匹配问题的时候,书上的关于KMP的算法的介绍总是理解不了.看了一遍代码总是很快的忘掉,后来决定好好分解一下KMP算法,算是给自己加深印象. 在将KMP字串匹配问题的时候,我们先来回顾一下字串匹配的暴力解法: 假设字符串str为: "abcgbabcdh",  字串substr为: "abcd" 从第一个字符开始比较,显然两个字符串的第一个字符相等('a'=='a'),然后比较第二个字符也相等('b'=='b'),继续下去,我们发现第4个字符不相等了('g'!

  • Python实现字符串匹配的KMP算法

    kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法).KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息. #! /usr/bin/python # coding=utf-8 """ 基于这篇文章的python实现 http://bl

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • C C++算法题解LeetCode1408数组中的字符串匹配

    目录 题目描述 整理题意 解题思路分析 优化 具体实现 复杂度分析 代码实现 暴力 暴力 + 优化 KMP 总结 题目描述 题目链接:1408. 数组中的字符串匹配 给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo

  • python3 kmp 字符串匹配的方法

    先声明,本人菜鸟一个,写博客是为了记录学习的过程,以及自己的理解和心得,可能有的地方写的不好,希望大神指出... 抛出问题 给定一个文本串test_str(被匹配的字符串)和模式串pat_str(需要从文本串中匹配的字符串),从文本串test_str中找出模式串pat_str第一次出现的位置,没有的话返回 -1 暴力方式 在说kmp之前,我们先来讲下"暴力方式",也就是说我们最原始的方法. text_str = 'asdabcdace' pat_str = 'abcdace' def

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

随机推荐