返回顶部

收藏

KMP算法原理与实现(精简)

更多

思想:使源字符串中的下标不回溯,利用模式字符串自身的相关性,减少模式字符串中下标回溯的距离。从而减少比较的次数。

关键问题: 分析模式字符串,得出 部分匹配值数组。

原理参考此处。

具体实现:

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void get_next(int next[], char source[], int n);//获取部分匹配字符数组
int Index_KMP(char* s_string, char* t_string, int pos);//返回源字符串s_string中pos开始 与t_string匹配的第一个字符串首字母下标,无匹配返回0

int main()
{
    char *source_str = "BBC ABCDAB ABCDABCDABDE";
    char *t_str = "ABCDAB";//模式串

    printf("%d\n", Index_KMP(source_str, t_str, 8));

    return 0;
}

void get_next(int next[], char source[], int n)
{
    int i = 0;
    next[0] = 0;
    for(i = 1; i < n; i++)
    {
        if(source[i] == source[next[i-1]])
            next[i] = next[i-1] + 1;
        else
            next[i] = 0;
    }
}

int Index_KMP(char* s_string, char* t_string, int pos)
{
    int i = pos;//指向 s_string的起始下标
    int j = 0;//指向 t_string的起始下标
    int t_len = strlen(t_string);
    int s_len = strlen(s_string);
    int* t_next = (int*)malloc(sizeof(int)*t_len);
    int m;

    get_next(t_next, t_string, t_len);//获取t_string的部分匹配字符数组
    for(m = 0; m < t_len; m++)
        printf("%d ",t_next[m]);
    printf("\n");

    while( (i<s_len)&amp;&amp;(j<t_len) )
    {
        if(s_string[i] == t_string[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j == 0)
            {
                i++; //源字符串下表前移动
            }
            else
            {
                m = j - t_next[j-1];//需回溯的位数
                j = j - m;//设置下一次的起始坐标   
            }
        }
   }
    free(t_next);

    if(j==t_len)
        return i-t_len;
    else
        return 0;
}

来自:http://blog.csdn.net/youxin2012/article/details/17083261

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论