【算法拾遗·字符串篇】KMP字符串匹配算法

作者:神秘网友发布时间:2020-09-30 15:04:01

【算法拾遗·字符串篇】KMP字符串匹配算法

KMP字符串匹配算法

问题描述
暴力搜索匹配
KMP匹配
- 图解:
- - 1、构建最长公共前后缀表
  - 2、KMP匹配操作
- 总结：
- 代码：

问题描述

已知字符串 text 和字符串 pattern，
问 pattern 是否为 text 的子串

暴力搜索匹配

int main() {
    const char *pattern = "ACTG";
    const char *text = "CGTACGTACCTAGCACTGACTAGCCA"; 
    int cnt = search(pattern, text);
    printf("%d\n", cnt);
    return 0;
}

int search(const char *pattern, const char *text) {
    int M = strlen(pattern);
    int N = strlen(text);
    printf("%d\n%d\n", strlen(pattern), strlen(text));
    for (int i = 0; i < N - M; i++) {
        int j;
        for (j = 0; j < M; j++) {
            if (*(pattern+j) != *(text+j+i))
                break;
        }
        // pat 全都匹配了
        if (j == M) return i;
    }
    return -1;
}

时间复杂度：O(M*N)
其中M为子串长度，N为母串长度

KMP匹配

1、构建最长公共前后缀表

（1）给定两个字符串T， P
【算法拾遗·字符串篇】KMP字符串匹配算法
（2）建立P的最长公共前后缀表

（举例）abab的最长公共前后缀是：ab

（3）获得结果
（4）为方便日后的边界判定，去掉最后一位（用不到），添加头部指示符

2、KMP匹配操作

（1）当 P[3] != T[3]时，前缀表prefix[3] = 1，即可以将P[1]移至T[3]处继续向后匹配（此时的P[1]之前部分与对应的T[3]之前的部分相同，故不用再做比较）
【算法拾遗·字符串篇】KMP字符串匹配算法

（2）当 P[1] != T[3+1]时，前缀表prefix[1] = 0，即可以将P[0]移至T[3+1]处继续向后匹配。

（3）当 P[0] != T[4+0]时，前缀表prefix[0] = -1，即此时T[4]不匹配 P 中任意字符，故 P 向后移一位对齐下一位 T。
【算法拾遗·字符串篇】KMP字符串匹配算法
内容来自视频:正月点灯笼.

本质：
对串的前缀进行去处理
得到所有可能出现匹配的位置
从而减少不必要的位移

1、关于 pattern 建立最长公共前后缀表prefix：
如何最快查找其公共前后缀 {参考动态规划}

2、通过 prefix 辅助 pattern 对 text 的匹配
如何借助prefix进行移位匹配操作
{匹配成功/失败（如何更新索引状态）}

#include <stdio.h>
#include <stdlib.h>
#define LENLIMIT 128

// 输入信息
int get_text(char demo[]);
// 建立pattern字符串的公共前后缀长度表prefix
void prefix_table(char pattern[], int prefix[], int n);
// 为方便匹配，故向右移动prefix
void move_prefix(int prefix[], int n);
void show_prefix(int prefix[], int n);
void kmp_search(char text[], char pattern[], \
int prefix[], int text_len, int pattern_len);

int main(int argc, char const *argv[]) {
    
    char *text = (char *)malloc(sizeof(char)*LENLIMIT);
    char *pattern = (char *)malloc(sizeof(char)*LENLIMIT);
    int *prefix = (int *)malloc(sizeof(int)*LENLIMIT);

    printf("typein text\t: ");
    int text_len = get_text(text);
    printf("typein pattern\t: ");
    int pattern_len = get_text(pattern);

    printf("text\t: %s\n", text);
    printf("pattern\t: %s\n", pattern);

    prefix_table(pattern, prefix, pattern_len);
    show_prefix(prefix, pattern_len);
    kmp_search(text, pattern, prefix, \
    text_len, pattern_len);

    free(pattern);
    free(prefix);
    return 0;
}

// 动态数组的赋值方法：
// 数组指针【char *demo】<=>【char demo[]】<=>【demo[i]】
int get_text(char demo[]) {
    char ch;
    int i = 0;
    while((ch=getchar())!='\n') {
        demo[i++] = ch;
        demo[i] = '\0';
    }
    return i;
}

void prefix_table(char pattern[], int prefix[], int n) {
    /* 操作对象：pattern的子数组
     * i = 1~n-1
     * len为当前最长公共前后缀记录
     * 1、前一刻len的后一位（新晋前缀） 等于 当前i位置（新晋后缀）：
     *      len+1并赋给pattern[i], i++
     * 2、否则
     * 2.1、len = 0: pattern[i] = 0, i++
     * 2.2、len > 0: 更新len为len-1时的prefix, 继续寻找len
     */
    prefix[0] = 0;
    int i = 1;
    int len = 0;
    printf("%d\n", n);
    while (i < n) {
        // 通常情况，动态规划
        if (pattern[i] == pattern[len]) {
            prefix[i] = ++len;
            i++;
        }
        else {
            // 非边界异常情况，左斜处取长度
            if (len > 0) {
                len = prefix[len - 1];
            }
            // 边界异常情况，等0后移
            else {
                prefix[i] = len;
                i++;
            }
        }
    }
    // 为方便后续匹配
    move_prefix(prefix, n);
}

void move_prefix(int prefix[], int n) {
    int i;
    for (i=n-1; i>0; i--) {
        prefix[i] = prefix[i-1];
    }
    prefix[0] = -1;
}

void show_prefix(int prefix[], int n) {
    int i;
    for (i=0; i<n; i++) {
        printf("%d\t", prefix[i]);
    }
    printf("\n");
}

void kmp_search(char text[], char pattern[], \
int prefix[], int text_len, int pattern_len) {
    /* 各数组的索引声明
     * text[i]
     * pattern[j]
    */
    int i = 0;
    int j = 0;
    while (i<text_len) {
        if (text[i]==pattern[j]) {
            // pattern 完全匹配 
            if (j==pattern_len-1) {
                printf("At: %d, get!\n", i-j);
                j = prefix[j]+1;  //不停下来，继续往下比 
            }
            // 当前位匹配且继续往下比
            else {
                j++;
            }
            i++;
        }
        else {
            // pattern 首位不匹配时，text后移(i+1)
            if (prefix[j]==-1) {
                i++;
            } 
            // pattern 迁移到公共前缀记录处
            else {
                j = prefix[j];
            }
        }
    } 
    printf("Over...\n");
}

时间复杂度：O(N+M)
其中M为子串长度，N为母串长度

【算法拾遗·字符串篇】KMP字符串匹配算法相关教程

阿里P9架构师力荐的超火算法笔记在大厂面试时到底是有什么不可或

阿里P9架构师力荐的超火算法笔记，在大厂面试时到底是有什么不可或缺的地位？程序员到底需不需要学习算法?这个问题被争论的次数绝对不亚于“Java是不是最好的语言”“VIM和Emacs谁是最好的编辑器”“程序员是不是需要学习数学”。为了避免陷入这样的争论里
国庆临近字节后端开发3+4面终于拿到秋招第一个offer算法+MySQL+M

国庆临近，字节后端开发3+4面，终于拿到秋招第一个offer，算法+MySQL+MyCat+微服务+并发编程，给到60*14 字节跳动，先面了data部门，3面技术面之后hr说需要实习转正，拒绝，之后另一个部门捞起，四面技术面，已oc 分享面经，希望对大家有所帮助，秋招顺利在
内置数据结构字符串

内置数据结构字符串字符串的表示方式字符串的表示方式：字符串或串(String)是由数字、字母、下划线组成的一串字符。Python 里面最常见的类型。可以简单地通过在引号间(单引号,双引号和三引号)包含字符的方式创建它。一个反斜线加一个单一字符可以表示一
C语言学习记录（二）——字符串、字符数组

C语言学习记录（二）——字符串、字符数组学习足迹前言一、printf基本用法 1. 变量类型 2. 常用设置二、字符数组（串）定义 1. 字符数组定义单个字符的定义及初始化字符串的定义及初始化定义出错啦~ 2. 使用字符指针定义字符串注意补充总结前言在
普利姆算法解决最短修路问题

普利姆算法解决最短修路问题 1、应用场景-修路问题 2、最小生成树 3、普利姆算法介绍 4、普利姆算法的最为简单的理解（重点）：理论上7个点要6条路就可以连通，随便从一个结点（村庄）出发（假设为A），先找该结点和邻居结点（村庄）距离最小的结点（村庄）
【算法】合并两个有序数组【LeetCode】

【算法】合并两个有序数组【LeetCode】文章目录一、题目二、说明三、示例四、代码实现 1. 思路一：一、题目给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。二、说明初始化 nums1 和 nums2 的元素
把并行化的思想用在编解码验证算法上的实践

把并行化的思想用在编解码验证算法上的实践编码验证算法是一种验证数据序列编码格式的算法，比较典型的有UTF-8编码验证算法。UTF-8验证算法用于检查数据序列是否符合UTF-8编码规范，比如说对常用UTF-8编码的邮件、网页及应用数据做编码验证时，就可以使用UTF
2020中国华录杯·数据湖算法大赛—定向算法赛（吸烟打电话检测）

2020中国华录杯·数据湖算法大赛—定向算法赛（吸烟打电话检测）baseline-tensorflow2-python3.6 文章目录 1.赛事背景 1.主办方 2.赛事介绍 2.baseline 2.1 文件夹结构 2.2 demo 1. 01_train_test_split.py 2. 02_tf2_mobilev2_classes.py 3. 03_predict.py 3