目的

给字符串Text,eg."ACABABCABAAABABABBBBABA"
给字符串Pattern,eg."ABABCABAA"
要在Text中找到Pattern。

思路

  1. 求Pattern字符串的前缀表Prefix[],并将Prefix[0]位为-1,依次后移。
  2. 依次匹配,当匹配到K位发现不符,就移动Prefix[K]位和Text[K]对齐。

KMP思路

代码实现

前缀表的计算

欲求当前的可以参考前一短的前缀,只需要比较此串的最后一位和前一段的+1位即可。

  1. 若一致,则为上一个的值+1
  2. 反之,若前一个为0,直接为0看下一位;不为0,移动其对应的-1为与当前位对其。

前缀表实现

然后再变-1并移动即可。

KMP匹配

i->Text[n]
j->Pattern[m]
从前匹配,一样则i,j后移,反之则看前缀表对齐。

search

Code

代码在此

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

void prefix_table(char pattern[], int prefix[], int n){
    prefix[0] = 0;
    int len = 0;
    int i = 1;
    while(i < n){
        if(pattern[i] == pattern[len]){
            len++;
            prefix[i] = len;
            i++;
        }
        else{
            if(len > 0)
                len = prefix[len-1];
            else{
                prefix[i] = 0;
                i++;
            }
        }
    }
} 

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

void kmp_search(char text[],char pattern[]){
    int n = strlen(pattern);
    int m = strlen(text);
    
    int* prefix = (int *)malloc(sizeof(int) * n);
    prefix_table(pattern,prefix,n);
    move_prefix_table(prefix,n);
    
    int i = 0,j = 0;
    while(i < m){
        if(j == n-1 && text[i] == pattern[j]){
            printf("AT %d\n",i-j);
            j = prefix[j];
        }
        if(text[i] == pattern[j]){
            i++;
            j++;
        }
        else{
            j = prefix[j];
            if(prefix[j] = -1){
                i++;j++;
            }
        }
    }
}

int main()
{
    char pattern[] = "ABABCABAA";
    char text[] = "ACABABCABAAABABABBBBABA";
    kmp_search(text,pattern);
    return 0;
}

看正月点灯笼大神的视频弄明白的,觉得还不是很复杂,跟后缀比起来还好...

其他

最近的几个项目实验:

1.刚刚班长找我弄班主任推荐的一个项目。
有关利用图像识别系统来为盲人检测盲道,老师是从一篇本校硕士生论文得到的想法,我瞬间就被吸引了,果断加入。
知识点的漏洞让我面临很多问题:

  1. 图片识别算法
  2. 训练框架
  3. Android相关技术

2.学校信息化处的学校企业公众号建设。

  1. SQL Server

啥也不会现在连环境还没搞定..

啊!想当个懒人咋这么难

Last modification:July 7th, 2020 at 11:28 pm
请赏我杯奶茶,让我快乐长肉