嵌入式 KMP算法详解及各种应用和BF算法提及

2024-01-05 11:48
文章标签 算法 应用 详解 嵌入式 kmp bf 提及

本文主要是介绍嵌入式 KMP算法详解及各种应用和BF算法提及，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KMP算法详解：
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下：
1) next[j]=-1  j=0
2) next[j]=max k:0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j]=0  其他
如：
P      a    b   a    b   a
j       0   1    2   3   4
next -1  0    0   1   2
即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
代码实现如下：

[cpp] view plaincopy
  1. int KMPMatch(char *s,char *p)  
  2. {  
  3.     int next[100];  
  4.     int i , j;  
  5.     i = 0;  
  6.     j = 0;  
  7.     getNext(p , next);  
  8.     while(i < strlen(s))  
  9.     {  
  10.         if(j == -1 || s[i] == p[j])  
  11.         {  
  12.             i++;  
  13.             j++;  
  14.         }  
  15.         else  
  16.         {  
  17.             j = next[j];       //消除了指针i的回溯  
  18.         }  
  19.         if(j == strlen(p))  
  20.             return i - strlen(p);  
  21.     }  
  22.     return -1;  
  23. }  
因此KMP算法的关键在于求算next[]数组的值，即求算模式串每个位置处的最长后缀与前缀相同的长度， 而求算next[]数组的值有两种思路，第一种思路是用递推的思想去求算，还有一种就是直接去求解。
  1、按照递推的思想：
   根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
   1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;
   2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]。
   因此可以这样去实现：
[cpp] view plaincopy
  1. void getNext(char *p,int *next)  
  2. {  
  3.     int j,k;  
  4.     next[0] = -1;  
  5.     j = 0;  
  6.     k = -1;  
  7.     while(j < strlen(p) - 1)  
  8.     {  
  9.         if(k == -1 || p[j] == p[k])    //匹配的情况下,p[j]==p[k]  
  10.         {  
  11.             j++;  
  12.             k++;  
  13.             next[j] = k;  
  14.         }  
  15.         else                   //p[j]!=p[k]  
  16.             k = next[k];  
  17.     }  
  18. }  
   2、直接求解方法
[cpp] view plaincopy
  1. void getNext(char *p,int *next)  
  2. {  
  3.     int i , j , temp;  
  4.     for(i = 0 ; i < strlen(p) ; ++i)  
  5.     {  
  6.         if(i == 0)  
  7.         {  
  8.             next[i] = -1;     //next[0]=-1  
  9.         }  
  10.         else if(i == 1)  
  11.         {  
  12.             next[i] = 0;      //next[1]=0  
  13.         }  
  14.         else  
  15.         {  
  16.             temp = i - 1;  
  17.             for(j = temp ; j > 0 ; --j)  
  18.             {  
  19.                 if( equals(p , i , j) )  
  20.                 {  
  21.                     next[i] = j;   //找到最大的k值  
  22.                     break;  
  23.                 }  
  24.             }  
  25.             if(j == 0)  
  26.                 next[i] = 0;  
  27.         }  
  28.     }  
  29. }  
  30.    
  31. bool equals(char *p,int i,int j)     //判断p[0...j-1]与p[i-j...i-1]是否相等   
  32. {  
  33.     int k = 0;  
  34.     int s = i - j;  
  35.     for( ; k <= j - 1 && s <= i - 1 ; k++ , s++)  
  36.     {  
  37.         if(p[k] != p[s])  
  38.             return false;  
  39.     }  
  40.     return true;  
  41. }  
http://poj.org/problem?id=2406

给定一个字符串，问最多是多少个相同子串不重叠连接构成。

KMP的next数组应用。这里主要是如何判断是否有这样的子串，和子串的个数。

若为abababa，显然除其本身外，没有子串满足条件。而分析其next数组，next[7] = 5，next[5] = 3，next[3] = 1，即str[2..7]可由ba子串连接构成，那怎么否定这样的情况呢？很简单，若该子串满足条件，则len%sublen必为0。sunlen可由上面的分析得到为len-next[len]。

因为子串是首尾相接，len/sublen即为substr的个数。

若L%(L-next[L])==0,n = L/(L-next[L]),else n = 1

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<cstdio>  
  3. using namespace std;  
  4.   
  5. char pattern[1000002];  
  6. int next[1000002];  
  7.   
  8. /* 
  9. kmp算法，需要首先求出模式串的next函数值 
  10. next[j] = k,说明 p0pk-1 == pj-kpj-1,也就是说k为其前面相等串的长度 
  11. */  
  12. void get_nextval(const char* pattern)  
  13. {  
  14.     int i=0,j=-1;  
  15.     next[0]= -1;  
  16.     while(pattern[i] != '\0')  
  17.     {  
  18.         if(j== -1 || pattern[i]== pattern[j] )     //pattern[i]表示后缀的单个字符，pattern[j]表示前缀的单个字符  
  19.         {  
  20.             ++i;  
  21.             ++j;  
  22.             if(pattern[i] != pattern[j])  
  23.                 next[i]=j;  
  24.             else  
  25.                 next[i]=next[j];  
  26.         }  
  27.         else  
  28.             j=next[j];    //若j值不相同，则j值回溯  
  29.     }  
  30. }//get_nextval  
  31.   
  32. int main(void)  
  33. {  
  34.     int len;  
  35.     while(scanf("%s",pattern)!=EOF)  
  36.     {  
  37.         if(pattern[0]=='.')  
  38.             break;  
  39.         len=strlen(pattern);  
  40.   
  41.         get_nextval(pattern);             
  42.           
  43.         if(len%(len-next[len])==0)  
  44.             printf("%d\n",len/(len-next[len]));  
  45.         else  
  46.             printf("1\n");  
  47.               
  48.     }  
  49.     return 0;  
  50. }  

http://poj.org/problem?id=1961

大意：
   定义字符串A,若A最多由n个相同字串s连接而成，则A=s^n,如"aaa" = "a"^3,"abab" = "ab"^2
   "ababa" = "ababa"^1
   
给出一个字符串A，求该字符串的所有前缀中有多少个前缀SA= s^n（n>1）
输出符合条件的前缀长度及其对应的n

  如aaa
  前缀aa的长度为2,由2个'a'组成
  前缀aaa的长度为3，由3个"a"组成

  分析：KMP
  若某一长度L的前缀符合上诉条件，则
    1.next[L]!=0(next[L]=0时字串为原串，不符合条件)
 2.L%(L-next[L])==0（此时字串的长度为L/next[L]）

 对于2：有str[0]....str[next[L]-1]=str[L-next[L]-1]...str[L-1]
        =》str[L-next[L]-1] = str[L-next[L]-1+L-next[L]-1] = str[2*(L-next[L]-1)];
  假设S = L-next[L]-1;则有str[0]=str[s]=str[2*s]=str[3*s]...str[k*s],对于所有i%s==0,均有s[i]=s[0]
  同理，str[1]=str[s+1]=str[2*s+1]....
        str[j]=str[s+j]=str[2*s+j]....
  综上，若L%S==0,则可得L为str[0]...str[s-1]的相同字串组成，
  总长度为L,其中字串长度SL = s-0+1=L-next[L],循环次数为L/SL
   故对于所有大于1的前缀，只要其符合上述条件，即为答案之一

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstring>  
  4. using namespace std;  
  5.   
  6. char pattern[1000002];  
  7. int next[1000002];  
  8.   
  9. /* 
  10. kmp算法，需要首先求出模式串的next函数值 
  11. next[j] = k,说明 p0pk-1 == pj-kpj-1,也就是说k为其前面相等串的长度 
  12. */  
  13. void get_nextval(const char* pattern)  
  14. {  
  15.     int i=0,j=-1;  
  16.     next[0]= -1;  
  17.     while(pattern[i] != '\0')  
  18.     {  
  19.         if(j== -1 || pattern[i]== pattern[j] )  
  20.         {  
  21.             ++i;  
  22.             ++j;  
  23.             next[i]=j;  
  24.         }  
  25.         else  
  26.             j=next[j];  
  27.     }  
  28. }//get_nextval  
  29.   
  30. int main(void)  
  31. {  
  32.     int i,len,n,j=1;  
  33.     while(scanf("%d",&n)!=EOF)  
  34.     {  
  35.         if(!n)  
  36.             break;  
  37.         scanf("%s",pattern);  
  38.         len=strlen(pattern);  
  39.   
  40.         get_nextval(pattern);  
  41.       
  42.         printf("Test case #%d\n",j++);  
  43.         for(i=2;i<=len;i++)  
  44.         {  
  45.             if(i%(i-next[i])==0 && i/(i-next[i])>1)  
  46.                 printf("%d %d\n",i,i/(i-next[i]));  
  47.         }  
  48.         printf("\n");  
  49.               
  50.     }  
  51.     return 0;  
  52. }  

http://poj.org/problem?id=2752
 大意：
给出一个字符串A,求A有多少个前缀同时也是后缀，从小到大输出这些前缀的长度。

分析：KMP
对于长度为len的字符串，由next的定义知：
A[0]A[1]...A[next[len]-1]=A[len-next[len]]...A[len-1]此时A[0]A[1]...A[next[len]-1]为一个符合条件的前缀
有A[0]A[1]....A[next[next[len]]-1] = A[len-next[next[len] - next[next[len]]]...A[next[len]-1],故A[0]A[1]....A[next[next[len]]-1]也是一个符合条件的前缀
故从len=>next[len]=>next[next[len]] ....=>直到某个next[]为0均为合法答案，注意当首位单词相同时，也为答案。

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstring>  
  4. #include<vector>  
  5. using namespace std;  
  6.   
  7. char pattern[400002];  
  8. int next[400002];  
  9.   
  10. /* 
  11. kmp算法，需要首先求出模式串的next函数值 
  12. next[j] = k,说明 p0pk-1 == pj-kpj-1,也就是说k为其前面相等串的长度 
  13. */  
  14. void get_nextval(const char* pattern)  
  15. {  
  16.     int i=0,j=-1;  
  17.     next[0]= -1;  
  18.     while(pattern[i] != '\0')  
  19.     {  
  20.         if(j== -1 || pattern[i]== pattern[j] )  
  21.         {  
  22.             ++i;  
  23.             ++j;  
  24.             next[i]=j;  
  25.         }  
  26.         else  
  27.             j=next[j];  
  28.     }  
  29. }//get_nextval  
  30.   
  31. int main(void)  
  32. {  
  33.     int i,len,n;  
  34.     vector<int>ans;  
  35.     while(scanf("%s",pattern)!=EOF)  
  36.     {  
  37.         ans.clear();  
  38.         len=strlen(pattern);  
  39.         get_nextval(pattern);  
  40.         n=len;  
  41.         while(n)  
  42.         {  
  43.             ans.push_back(n);  
  44.             n=next[n];  
  45.         }  
  46.         if(pattern[0]==pattern[n-1])   //首部、尾部字符相同  
  47.             ans.push_back(1);  
  48.   
  49.         i=ans.size()-1;  
  50.         for(;i>0;i--)  
  51.             printf("%d ",ans[i]);  
  52.         printf("%d\n",ans[0]);  
  53.     }  
  54.     return 0;  
  55. }  

在介绍KMP算法之前，先介绍一下BF算法。

一.BF算法

    BF算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。

    举例说明：

    S:  ababcababa

    P:  ababa

　 BF算法匹配的步骤如下

           i=0                                   i=1                             i=2                         i=3                          i=4

  第一趟:ababcababa         第二趟:ababcababa      第三趟:ababcababa    第四趟:ababcababa    第五趟:ababcababa

             ababa                            ababa                          ababa                        ababa                       ababa

            j=0                                   j=1                            j=2                         j=3                         j=4(i和j回溯)

 

              i=1                                 i=2                           i=3                            i=4                        i=3

 第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababcababa   第十趟:ababcababa

              ababa                              ababa                           ababa                        ababa                        ababa

             j=0                                  j=0                           j=1                           j=2(i和j回溯)            j=0

 

              i=4                                    i=5                          i=6                           i=7                          i=8

第十一趟:ababcababa       第十二趟:ababcababa    第十三趟:ababcababa   第十四趟:ababcababa   第十五趟:ababcababa

                     ababa                               ababa                           ababa                          ababa                          ababa

               j=0                                    j=0                         j=1                            j=2                         j=3

 

                    i=9

第十六趟:ababcababa

                       ababa

                    j=4(匹配成功)

代码实现:

复制代码 
int BFMatch(char *s,char *p)
{int i,j;i=0;while(i<strlen(s)){j=0;while(s[i]==p[j]&&j<strlen(p)){i++;j++;}if(j==strlen(p))return i-strlen(p);i=i-j+1;                //指针i回溯
    }return -1;    
}
复制代码
 　 其实在上面的匹配过程中，有很多比较是多余的。在第五趟匹配失败的时候，在第六趟，i可以保持不变，j值为2。因为在前面匹配的过程中，对于串S，已知s0s1s2s3=p0p1p2p3，又因为p0!=p1!，所以第六趟的匹配是多余的。又由于p0==p2,p1==p3，所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

二.KMP算法

    KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。

　 在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

　 对于next[]数组的定义如下：

　1) next[j] = -1  j = 0

　2) next[j] = max(k): 0<k<j   P[0...k-1]=P[j-k,j-1]

　3) next[j] = 0  其他

　如：

　P      a    b   a    b   a

　j      0    1   2    3   4

 next    -1   0   0    1   2

　即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]

　因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

代码实现如下：

复制代码 
int KMPMatch(char *s,char *p)
{int next[100];int i,j;i=0;j=0;getNext(p,next);while(i<strlen(s)){if(j==-1||s[i]==p[j]){i++;j++;}else{j=next[j];       //消除了指针i的回溯
        }if(j==strlen(p))return i-strlen(p);}return -1;
}
复制代码

　　因此KMP算法的关键在于求算next[]数组的值，即求算模式串每个位置处的最长后缀与前缀相同的长度， 而求算next[]数组的值有两种思路，第一种思路是用递推的思想去求算，还有一种就是直接去求解。 

1.按照递推的思想：

   根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]

   1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;

   2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]。

   因此可以这样去实现：

复制代码 
void getNext(char *p,int *next)
{int j,k;next[0]=-1;j=0;k=-1;while(j<strlen(p)-1){if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]
        {j++;k++;next[j]=k;}else                   //p[j]!=p[k]k=next[k];}
}
复制代码
 
   2.直接求解方法
复制代码 
void getNext(char *p,int *next)
{int i,j,temp;for(i=0;i<strlen(p);i++){if(i==0){next[i]=-1;     //next[0]=-1
        }else if(i==1) {next[i]=0;      //next[1]=0
        }else{temp=i-1;for(j=temp;j>0;j--){if(equals(p,i,j)){next[i]=j;   //找到最大的k值break;}}if(j==0)next[i]=0;}}
}bool equals(char *p,int i,int j)     //判断p[0...j-1]与p[i-j...i-1]是否相等  
{int k=0;int s=i-j;for(;k<=j-1&&s<=i-1;k++,s++){if(p[k]!=p[s])return false;}return true;
}

这篇关于嵌入式 KMP算法详解及各种应用和BF算法提及的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/572764。

相关文章

Linux换行符的使用方法详解

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将
阅读更多...
详解C#如何提取PDF文档中的图片

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片，如艺术画作、设计素材、报告图表等，提取图片可以将这些图像资源进行单独保存，方便后续在不同的项目中使
阅读更多...
Android中Dialog的使用详解

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog（对话框）是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog（
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Java中StopWatch的使用示例详解

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类，使用它
阅读更多...
Java进行文件格式校验的方案详解

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip
阅读更多...
Java实现时间与字符串互相转换详解

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串（一）使用预定义格式（二）自定义格式二、字符串解析为日期（一）解析ISO格式字符串（二）解析自定义
阅读更多...
springboot security快速使用示例详解

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》：本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s
阅读更多...
Python中随机休眠技术原理与应用详解

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2
阅读更多...
一文详解SpringBoot响应压缩功能的配置与优化

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2