kmp算法_Bill_Hoo专栏

你是否正在寻找关于kmp算法的内容？让我把最实在的东西奉献给你：

博主的更多文章>>

【KMP算法详解——适合初学kmp算法的朋友】

标签：

原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任，。

相信很（包括自己）初识KMP算法的时候始终是丈二和尚摸不着头脑，要么完全不知所云，要么看不懂书上的解释，要么自己觉得好像心里了解kmp算法的意思，却说不出个究竟，所谓知其然不知其所以然是也。

经过七八个小时地仔细研究，终于感觉自己能说出其所以然了，又觉得数据结构书上写得过于简洁，不易于初学者接受，于是决定把自己的理解拿出来与大家分享，希望能抛砖引玉，这便是Bill写这篇文章想要得到的最好结果了

-----------------------------------谨以此文，献给刚接触kmp算法的朋友，定有不足之处，望大家指正----------------------------------------

【kmp算法简介】

KMP算法是一种改进后的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称kmp算法）。通过一个辅助函数实现跳过扫描不必要的目标串字符，以达到优化效果。

【传统字符串匹配算法的缺憾】

Bill认为，对于一种优化的算法，既要知道优化的细节，也更应该了解它的前身（至于KMP是否基于传统算法，我不清楚，这里只作语境上的前身），了解是什么原因导致了人们要去优化它，因此加入了这一段：

请看以下传统字符串匹配的代码：

C++ code

void NativeStrMatching( ElemType Target[], ElemType Pattern[] )
{
register int TarLen = 0;// Length of Target
register int PatLen = 0;// Length of Pattern

// Compute the length of Pattern
while( '\0' != Pattern[PatLen] )
PatLen++;

while( '\0' != Target[TarLen] )
{
int TmpTarLen = TarLen;
for(int i=0; i>页数 ( 1/2 )

以上就是关于kmp算法的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-3600-1.html