匹配字符串及KMP算法

news/2024/6/18 20:28:34 标签: 算法, c, 工作

cle class="baidu_pl">

cle_content" class="article_content clearfix">

content_views" class="htmledit_views">

匹配字符串常见的class="tags" href="/tags/SuanFa.html" title=算法>算法是࿰c;匹配字符串在被匹配字符串上一个一个向下移动࿰c;如果遇到不匹配࿰c;再回退回来࿰c;继续匹配下去。

举例：

被匹配字符串S "acabaabaabcacaabc"

匹配字符串（也叫模式字符串）P "abaabcac"

好比现在字符串到accolor:#ff0000">abaabcolor:#00c c c c">aabcacaabc（i=7）

color:#ff0000"> abaabcolor:#00c c c c">cac (j=5)

现在遇到不匹配时࿰c;P字符的j退到0位置࿰c;S字符i退到3位置

现在可以看一下KMPclass="tags" href="/tags/SuanFa.html" title=算法>算法࿰c;KMPclass="tags" href="/tags/SuanFa.html" title=算法>算法的思路是在S字符串的i值不回退（就是向上边的i值还是7）࿰c;只是将P中循环的j值匹配到j为2的位置࿰c;为什么是这样呢？

可以看一下P字符串的规律

color:#000000">color:#ff0000">abacolor:#ff0000">abcolor:#99ffff">cac

在c之前两个ab都是相同的࿰c;也就是说在c遇到不匹配的时候c前边的ab如果再来匹配的时候࿰c;在P前边的ab肯定能和c紧挨着的ab匹配上࿰c;那就等下次匹配的时候P开始的ab就不需要匹配了࿰c;将j直接移到j=2的位置a处开始匹配就可以了。这里仅仅是人工的来看࿰c;下边说一下class="tags" href="/tags/SuanFa.html" title=算法>算法的思路࿰c;class="tags" href="/tags/SuanFa.html" title=算法>算法比较专业的说法就是给P的每一位值计算出如果不匹配的时候这个j值应该是多少࿰c;向上边的讨论中࿰c;遇到在c这里不匹配了࿰c;再匹配的时候j的值应该是2.使用书本上的说法就是把这些值先放到next数组中,next数组中存放的就是j要

看到上边的分析࿰c;应该可以有点思路了吧。

就是在遇到不匹配的地方࿰c;将前边的字符串分为两半࿰c;像上边的abaab,然后用最大的长度将前后两部分分开࿰c;color:#ff0000">abacolor:#ff0000">ab࿰c;color:#000000">这里j就是匹配的值+1就是2。

class="tags" href="/tags/SuanFa.html" title=算法>算法初始化next[0] = -1;

c="http://hi.csdn.net/attachment/201110/15/0_1318697379DOeu.gif" alt="" />

class="tags" href="/tags/SuanFa.html" title=算法>算法的代码

void init_nextv()
{
int i=0,j=-1;
int p_len; /*模式串的长度*/
p_len=strlen(p);
nextv[0]=-1;
while(i<p_len-1)
    {
  if(j==-1 || p[i]==p[j])
  {
   ++i;++j;
   if(p[i]!=p[j])nextv[i]=j;
   else nextv[i]=nextv[j];
  }
  else j=nextv[j];
}
}