先给代码,有时间了再回来补注释和算法说明。---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int * get_prefix(const char * P)
{
int * pi = (int *)malloc(sizeof(int) * strlen(P));
pi[0] = -1;
int i = 1;
int j = -1;
while (P[i])
{
while (j >= 0 && P[j + 1] != P[i])
{
j = pi[j];
}
if (P[j + 1] == P[i])
{
++j;
}
pi[i] = j;
++i;
}
return pi;
}
void kmp_match(const char * T, const char * P)
{
const int * pi = get_prefix(P);
int i = 0;
int j = -1;
while (T[i])
{
while (j >= 0 && P[j + 1] != T[i])
{
j = pi[j];
}
if (P[j + 1] == T[i])
{
++j;
}
if (0 == P[j + 1])
{
printf("%s\n", T + i - j);
j = pi[j];
}
++i;
}
free(pi);
}
int main(int argc, char * argv[])
{
kmp_match("abcdabcdabcdabcd", "abc");
return 0;
}
参考:《算法导论》
---------------------------------------------------------------------------
/** Knuth-Morris-Pratt 字符串匹配算法的三种实现。* 匹配部分都一样,差异只在求 next 数组。:)*/#include <stdio.h>#include <stdlib.h>#include <string.h>/** 实现一*/char * kmp1(char * content, char * pattern){ int i; int j; int len; int * next; if (NULL == content || NULL == pattern) { return NULL; } len = strlen(pattern); next = (int *)malloc(len * sizeof(int)); /* Get the "next" array. */ next[0] = -1; for (i = 1; pattern[i] != 0; ++i) { j = next[i - 1]; while (pattern[i - 1] != pattern[j] && j >= 0) { j = next[j]; } next[i] = j + 1; } /* Match. */ i = 0; j = 0; while (content[i] && pattern[j]) { if (content[i] == pattern[j]) { ++i; ++j; } else { j = next[j]; if (-1 == j) { ++i; ++j; } } } free(next); if (pattern[j]) { return NULL; } else { return &content[i - j]; }}/** 实现二*/char * kmp2(char * content, char * pattern){ int i; int j; int len; int * next; if (NULL == content || NULL == pattern) { return NULL; } len = strlen(pattern); next = (int *)malloc(len * sizeof(int)); /* Get the "next" array. */ next[0] = -1; i = 0; j = -1; while (pattern[i]) { if (-1 == j || pattern[i] == pattern[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } /* Match. */ i = 0; j = 0; while (content[i] && pattern[j]) { if (content[i] == pattern[j]) { ++i; ++j; } else { j = next[j]; if (-1 == j) { ++i; ++j; } } } free(next); if (pattern[j]) { return NULL; } else { return &content[i - j]; }}/** 实现三** 实现二的改进,改进处见注释。*/char * kmp3(char * content, char * pattern){ int i; int j; int len; int * next; if (NULL == content || NULL == pattern) { return NULL; } len = strlen(pattern); next = (int *)malloc(len * sizeof(int)); /* Get the "next" array. */ next[0] = -1; i = 0; j = -1; while (pattern[i]) { if (-1 == j || pattern[i] == pattern[j]) { ++i; ++j; /* 此处是对实现二的改进。 */ if (pattern[i] == pattern[j]) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } /* Match. */ i = 0; j = 0; while (content[i] && pattern[j]) { if (content[i] == pattern[j]) { ++i; ++j; } else { j = next[j]; if (-1 == j) { ++i; ++j; } } } free(next); if (pattern[j]) { return NULL; } else { return &content[i - j]; }}int main(int argc, char * argv[]){ printf("%s\n", kmp1(argv[1], argv[2])); printf("%s\n", kmp2(argv[1], argv[2])); printf("%s\n", kmp3(argv[1], argv[2])); return 0;}参考:1. 《数据结构 (C 语言版)》,严蔚敏,吴伟民,P79-842. 字符串匹配的 KMP 算法详解3. KMP---------------------------------------------------------------------------
分享到:
相关推荐
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
KMP算法(Knuth-Morris-Pratt Algorithm)是一种改进的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,以达到快速匹配的目的...
KMP算法,全称Knuth-Morris-Pratt算法,是一种用于在一个主文本字符串(text)中查找一个模式字符串(pattern)的子串的高效算法。KMP算法的核心思想是利用模式字符串的特点,在匹配过程中尽可能地减少重复的字符...
让你迅速透彻的理解KMP算法! [1] http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm [KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of ...
KMP 算法,即 Knuth-Morris-Pratt 算法,是一种用于字符串匹配的经典算法。与朴素的字符串匹配算法相比,KMP 算法具有更高的效率,特别是在处理大型文本时。本文将介绍 KMP 算法的原理,并提供 C++示例代码来演示...
kmp算法
Knuth-Morris-Pratt 算法
KMP-knuth-morris-pratt-Python 在文本中查找模式的Knuth-Morris-Pratt算法的实现
KMP算法的核心思想是利用已经匹配过的信息,当发生不匹配时,知道一些字符肯定不会出现在模式串的某个位置,从而利用这些信息跳过一些不必要的比较。具体来说,KMP算法通过维护一个“部分匹配表”(也称为“失败函数...
KMP algorithm for matching string problem
KMP(Knuth-Morris-Pratt)算法是一种改进的字符串匹配算法,用于在一个文本字符串(T)中查找一个词(W)的出现位置。KMP算法的核心在于当字符串匹配发生不一致时,能知道已经部分匹配这个有效信息,利用这个信息...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
公里数Javascript 中的字符串搜索算法。安装npm install kmpbower install kmp用法 var kmp = require ( 'kmp' ) ;console . log ( kmp ( 'she sells seashells by the seashore' , 'shell' ) ) ; // 13console . ...
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种改进的字符串匹配算法。该算法的核心在于:当子串与主串不匹配时,它能知道已经有多少字符匹配了,并利用这些信息避免再次检查这些字符。相比于朴素匹配算法...
KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。KMP算法由D.E.Knuth,J.H.Morris和V.R.Pratt在 Brute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
KMP 算法(Knuth-Morris-Pratt) Rabin-Karp 算法 Boyer-Moore 算法 A* 搜索算法 Dijkstra 算法 Bellman-Ford 算法 Floyd-Warshall 算法 Kruskal 算法 Prim 算法 Edmonds-Karp 算法 Ford-Fulkerson 算法
克努斯-莫里斯-普拉特算法,KMP算法(Knuth–Morris–Pratt algorithm) 一种字符串查找算法。在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...