转载

字符串查找KMP算法

如果你用过ctrl+F这个快捷键，那么你有很大的概率使用过这个算法，这就是在待查找字符串（可能有成千上万个字符）中找出模式串（比较小，可能有几个字符），可能找到大于或者等于1次的位置。例如，在ababcd中找出abc。这里介绍算法思想，只给出了第一次出现的位置。

一.算法思想

传统算法是从匹配串第一字符开始和模式串比较，直到遇到不符合的字符，然后从匹配串的下一个字符开始，重复上面的过程。代码如下：

 void find(char t[],char p[]){     int m = strlen(t);     int n = strlen(p);     int i,j,k;//k:匹配串下标，j：模式串下标     for(k=0;k<m;k++){         j = 0;         i = k;         while(j<n){             if(p[j]==t[i]){                 i++;                 j++;             }else{                 break;             }         }         if(j==n){             printf("在%d处匹配/n",k);             break;         }     } }

KMP算法是这中算法的改进，在于不是i不是每次都移动一个位置，而是尽可能多的向后移动从而提高匹配效率。到底移动多少个位置，这就是KMP算法的关键。KMP算法维护了一个和模式串长度相同的数组，这个数组表示当前匹配到底最大前缀长度。比如abacab的最大前缀长度就是2，分别是前缀ab，后缀ab。而数组next就是[0,0,1,0,1,2]，可以利用这个信息直接跳过已经匹配到的前缀。

二.算法实现

 void makeNext(char p[],int next[]){     int q,k;//k是最大前缀长度，q是匹配串下标     next[0] = 0;     for(q=1,k=0;q<strlen(p);q++){         //若果不相等，那么就从上一次个字符串最长前缀处查看，依次类推         while(k>0&&p[q]!=p[k]){             k = next[k-1];         }         if(p[q]==p[k]){             k++;         }         next[q] = k;     } } void kmp(char t[],char p[]){     int next[3] = {0};     makeNext(p,next);     int i=0,j=0;//i是匹配串的下标，j是模式串的下标     while(i<strlen(t)&&j<strlen(p)){         //如果相等就继续比较         if(j==0||p[j]==t[i]){             i++;             j++;         }else{//不相等就要跳跃             j = next[j-1];         }     }     if(j>=strlen(p)){         printf("模式串匹配在%d处/n",i-j);     }else{         printf("匹配失败了");     } }

原文 http://www.cnblogs.com/bdbk/p/5202482.html

正文到此结束