• 字符串的模式匹配


    目录

    1.模式匹配

    (1)朴素模式的匹配方法

    (2)KMP算法

    (3)KMP优化方法


    1.模式匹配

    在主串中找到与模式串相同的子串,并返回子串的位置。模式匹配在串处理系统中是最重要的操作之一。

    (1)朴素模式的匹配方法

     主串的长度为m,子串的长度为n:将主串中所有长度为m的子串依次与模式串进行比较,直到找到一个完全匹配的子串或者所有的子串都不匹配为止,最多比较的次数为(m-n+1)。

    主串:qinghuadaxuecomputervisionmydream

    子串:vision

    1. #include
    2. #include
    3. #include
    4. #define maxn 100
    5. char S[maxn];
    6. char T[maxn];
    7. void substr(char *s,char r[maxn],int i,int n){
    8. int k=0;
    9. for(int j=i;j<(n+i);j++){
    10. r[k]=s[j];
    11. k++;
    12. }
    13. r[k]='\0';
    14. }
    15. //比较串是否相同
    16. bool Compare(char*s,char*t){
    17. int n=strlen(s);
    18. int m=strlen(t);
    19. for(int i=0;i
    20. if(s[i]!=t[i]){
    21. return false;
    22. }
    23. }
    24. return true;
    25. }
    26. //方法一
    27. int index_1(char*s,char*t,int m,int n){
    28. int pos=0;
    29. int len=m-n+1;
    30. while(pos<=len){
    31. char r[maxn];
    32. substr(s,r,pos,n);
    33. if(!Compare(r,t)){
    34. pos++;
    35. }else{
    36. return pos;
    37. }
    38. }
    39. return -1;
    40. }
    41. //方法二
    42. int index_2(char*s,char*t,int m,int n){
    43. int pos=0;
    44. int j=0,i=0;
    45. while(i
    46. if(s[i]==t[j]){
    47. i++;
    48. j++;
    49. }else{
    50. i=i-j+1;
    51. j=0;
    52. }
    53. }
    54. if(j>=n){
    55. return i-n;
    56. }else{
    57. return -1;
    58. }
    59. }
    60. int main(){
    61. printf("请输入主串: ");
    62. scanf("%s",&S);
    63. printf("\n");
    64. printf("请输入模式串: ");
    65. scanf("%s",&T);
    66. int m=strlen(S);
    67. int n=strlen(T);
    68. int pos=index_2(S,T,m,n);
    69. if(pos==-1){
    70. printf("匹配失败!\n");
    71. }else{
    72. printf("匹配成功!\n");
    73. printf("pos = %d\n",pos);
    74. }
    75. return 0;
    76. }

    注:上面的程序每个子串都要进行比较m个字符,共n-m+1个子串,因此上面的时间复杂度最坏的情况下O((n-m+1)*m)≈O(n*m)(主串n>>模式串m).因此对其进行改进的算法KMP。

    (2)KMP算法

    KMP算法是由D.E.Knuth,V.R.Pratt和J.H.Morris同时发现的,简称KMP算法。KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

    思想:每当一趟匹配过程中出现字符比较不等时,不需要回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后,继续进行比较。

    怎么实现指针i不需要回溯呢?也就是当主串中第i个字符与模式中第j个字符“失配”时,主串中第i个字符(指针i不回溯)应与模式中哪个字符再比较?

     

    next函数值
    j01234567
    模式串abaabcac
    next[j]01122312

     

    1. void get_next(char*t,int next[maxn],int n){
    2. int i=0;
    3. int j=-1;
    4. next[i]=-1;
    5. while(i
    6. if(j==-1||t[i]==t[j]){
    7. i++;
    8. j++;
    9. next[i]=j;
    10. }else{
    11. j=next[j];
    12. }
    13. }
    14. }

     

    1. #include
    2. #include
    3. #include
    4. #define maxn 100
    5. char S[maxn];
    6. char T[maxn];
    7. void get_next(char*t,int next[maxn],int n){
    8. int i=0;
    9. int j=-1;
    10. next[i]=-1;
    11. while(i
    12. if(j==-1||t[i]==t[j]){
    13. i++;
    14. j++;
    15. next[i]=j;
    16. }else{
    17. j=next[j];
    18. }
    19. }
    20. }
    21. int index(char*s,char*t,int next[maxn],int m,int n){
    22. int pos=0;
    23. int j=0,i=0;
    24. while(i
    25. if(j==-1||s[i]==t[j]){
    26. i++;
    27. j++;
    28. }else{
    29. j=next[j];
    30. }
    31. }
    32. if(j>=n){
    33. return i-n;
    34. }else{
    35. return -1;
    36. }
    37. }
    38. int main(){
    39. int next[maxn];
    40. for(int i=0;i
    41. next[i]=0;
    42. }
    43. printf("请输入主串: ");
    44. scanf("%s",&S);
    45. printf("\n");
    46. printf("请输入模式串: ");
    47. scanf("%s",&T);
    48. int m=strlen(S);
    49. int n=strlen(T);
    50. //得到next函数
    51. get_next(T,next,n);
    52. //abaabac=>0 1 1 1 2 3 1
    53. printf("next = ");
    54. for(int i=0;i
    55. printf("%d\t",next[i]);
    56. }
    57. printf("\n");
    58. //匹配位置
    59. int pos=index(S,T,next,m,n);
    60. if(pos==-1){
    61. printf("匹配失败!\n");
    62. }else{
    63. printf("匹配成功!\n");
    64. printf("pos = %d\n",pos);
    65. }
    66. return 0;
    67. }

     注:时间复杂度为O(n+m).

    (3)KMP优化方法

    方法一:首先求解出next函数值,然后根据函数值求解nextval函数值:

    next函数值
    j123456
    模式串ababaa
    next[j]011234

    1. //这里的char*t存储的字符是从1开始的
    2. void Get_nextval(char*t,int next,int nextval,int n){
    3. nextval[1]=0;
    4. for(int j=2;j<=n;j++){
    5. if(t[next[j]]==t[j]){
    6. nextval[j]=nextval[next[j]];
    7. }else{
    8. nextval[j]=next[j];
    9. }
    10. }
    11. }
    nextval函数值
    j123456
    模式串ababaa
    nextva;[j]000104

    方法二:直接使用下面的方法求解nextval函数值也可以

    1. void get_next(char*t,int next[maxn],int n){
    2. int i=0;
    3. int j=-1;
    4. nextval[i]=-1;
    5. while(i
    6. if(j==-1||t[i]==t[j]){
    7. i++;
    8. j++;
    9. if(t[i]!=t[j]){
    10. nextval[i]=j;
    11. }else{
    12. nextval[i]=nextval[j];
    13. }
    14. }else{
    15. j=next[j];
    16. }
    17. }
    18. }

  • 相关阅读:
    FreeRTOS学习笔记(二)
    【iMessage苹果推日历推位置推送】软件安装 UIApplication 的 registerForRemoteNotifications
    K8S(八):NFS + PV + ConfigMap + Service 部署MySQL
    JavaScript 62 JavaScript 版本 62.2 JavaScript ES5
    完美世界技术综合卷2017知识点
    Zookeeper 集群安装
    【springcloud】Feign的性能优化和最佳实践
    二分查找及例题
    `算法题解` `LuoGu` P4551 最长异或路径
    maven工程使用sonar扫描代码
  • 原文地址:https://blog.csdn.net/Keep_Trying_Go/article/details/126366552