image.png

:::info 在进行字符串匹配的相关程序中，看一个子串是否在一个主串里面，有著名的Brute-Force和基于此改进的KMP算法，具体学习记录如下： :::

Brute-Force

给出一个主串和一个子串 主串：s = ababcabcacbab 子串：t = abcac

①BF算法算是一种暴力算法，首先是查看t的第一字母a和上面s的第一个字母比较相同，所以接着比较比到各自的第三个字符也就是，aba、abc发现不同，

②再递推比较，t回到第一个字母a，这时s回到第二个字符（因为第一个字符已经比过了）相当于babcabcacbab和abcac两个字符串进行比较，很明显第一个字符就不一样，

③再递推比较……

按常理来思考，这样总能得出结果，但是在此基础上，可以有进一步的优化操作，怎么说？huaji1558a846ddf2e12b.jpeg
在上面的第②步里面，我们总是一步一步递推，那我们能不能一次性推好几步呢？就根据已经匹配了的那串字母。

具体表现为：①已经发现是第三个字符不同，那我们就根据前面两个相同的字符（ab）推出第②步推两步，为什么根据相同的ab，第②个步骤就可以一次性走两步？

KMP算法

算法详述

huaji1558a846ddf2e12b.jpeg先学会用，理论日后再补…… 🕊

image.png

计算next函数值

（3）串“ababaaababaa”的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 答案：C

j 1 2 3 4 5 6 7 8 9 10 11 12
t a b a b a a a b a b a a
next(j) 0 1 1 2 3 4 2 2 3 4 5 6

方法：
①next数组第一位永远是0，1；
②next(j) = 前序列相同元素个数 + 1；

eg：当t = 6：
前面的序列为ababa，可以看出相同的子序列为aba，相同元素个数为3，所以next(6) = 3 + 1 = 4

注意：不能“全覆盖”，比如当j = 2时候，前面的a不能看成a = a序列，这样就变成next(2) = 2了；

计算next函数修正值

（4）串“ababaabab”的nextval为（ ）。 A．010104101 B．010102101 C．010100011 D．010101011
答案：A

j 1 2 3 4 5 6 7 8 9
t a b a b a a b a b
next(j) 0 1 1 2 3 4 2 3 4
nextval(j) 0 1 0 1 0 4 1 0 1

方法：
①先列举出next(j)，求nextval(j)是基于next(j)的；
②求nextval(j)，先看求next(j)的值，记这个值为x；
③在表格中找出j = x的那一列，如果这一列的t值和②步骤中的t值相同，则结果为j = x这一列的nextval(j)值，如果不相同，则结果为所要求的那一列的next(j)值；

eg：当j = 5时：
此时next(j) = 3，就去j = 3那一列看到t = a，和j = 5一列的t值a相同，所以结果为j = 3一列的nextval值0

eg：当j = 6时：
此时next(j) = 4，就去j = 4那一列看到t = b，和j = 6一列的t值不相同，所以结果为j = 6一列的next值4

具体匹配情况

（2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

答案：
image.png

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef int Status;
  4. typedef int ElemType;
  5. #define OVERFLOW -1
  6. #define ERROR 0
  7. #define OK 1
  9. //------串的顺序存储结构-----
  10. #define MAXLEN 225
  11. typedef struct 
  12. {
  13.     char ch[MAXLEN + 1];    //存储串的一维数组，从下标为1的数组分量开始存储的，下标为0的分量闲置不用 
  14.     int length;             //串的当前长度
  15. }SString;
  17. //------串的堆式顺序存储结构-----
  18. typedef struct 
  19. {
  20.     char *ch;       //若是非空串，则按串长分配存储区，否则ch为NULL
  21.     int length;     //串的当前长度
  22. }HString;
  24. HString S, T;
  26. //-----串的链式存储结构-----
  27. #define CHUNKSIZE 80
  28. typedef struct Chunk
  29. {
  30.     char ch[CHUNKSIZE];
  31.     struct Chunk *next;
  32. }Chunk;
  33. typedef struct
  34. {
  35.     Chunk *head, *tail;     //串的头指针和尾指针
  36.     int length;             //串的当前长度
  37. }LString;
  39. // //1、生成串
  40. // StrAssign(&T, chars)
  42. // //2、复制
  43. // StrCopy(&T, S)
  45. // //3、判空
  46. // StrEmpty(S)
  48. // //4、比较
  49. // StrCompare(S, T)
  51. // //5、长度
  52. // StrLength(S)
  54. // //6、清空
  55. // ClearString(&S)
  57. // //7、联接
  58. // Concat(&T, S1, S2)
  60. // //8、子串
  61. // SubString(&Sub, S, pos, len)
  63. //9、串的模式匹配_BF算法 O(n * m)
  64. int Index_BF(HString S, HString T, int pos)
  65. {//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
  66.  //其中，T非空，1<=pos<=S.length
  67.     int i = pos, j = 1;                     //初始化
  68.     while(i <= S.length && j <= T.length)   //两串均未比较到串尾
  69.     {
  70.         if(S.ch[i] == T.ch[j])              //继续比较后继字符
  71.         {
  72.             i++;
  73.             j++;
  74.         }
  75.         else                                //指针后退重新开始匹配
  76.         {
  77.             i = i - j + 2;                  //i=i-j+1回到i的起点，+2到下一个字符
  78.             j = 1;
  79.         }
  80.     }
  81.     if(j > T.length)
  82.             return i - T.length;            //匹配成功，返回T在S中第一次出现的位置
  83.         else
  84.             return 0;
  85. }
  87. //9、串的模式匹配_KMP算法求next数组
  88. void get_next(HString, int next[])
  89. {//求模式串T的next函数值并存入数组next
  90.     int j = 1, t = 0;
  91.     next[1] = 0;
  92.     while(j < T.length)
  93.     {
  94.         if(t == 0 || T.ch[j] == T.ch[t])
  95.         {
  96.             t++;
  97.             j++;
  98.             next[j] = t;
  99.         }
  100.         else
  101.             t = next[t];
  102.     }
  103. }
  105. //9、串的模式匹配_KMP算法求nextval数组
  106. void get_nextval(HString T, int nextval[])
  107. {//求模式串T的next函数修正值并存入数组nextval
  108.     int j = 1, t = 0;
  109.     nextval[1] = 0;
  110.     while(j < T.length)
  111.     {
  112.         if(t == 0 || T.ch[j] == T.ch[t])
  113.         {
  114.             t++;
  115.             j++;
  116.             if(T.ch[j] != T.ch[t])
  117.                 nextval[j] = t;
  118.             else
  119.                 nextval[j] = nextval[t];
  120.         }
  121.         else
  122.             t = nextval[t];
  123.     }
  124. }
  126. //9、串的模式匹配_KMP算法 O(n + m)
  127. int Index_KMP(HString S, HString T, int pos, int next[])
  128. {//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
  129.  //其中，T非空，1<=pos<=S.length 
  130.     int i = pos, j = 1;
  131.     while(i <= S.length && j <= S.length)   //两个串均未比较到串尾
  132.     {
  133.         if(j == 0 || S.ch[i] == T.ch[i])    //继续比较后继字符
  134.         {
  135.             i++;
  136.             j++;
  137.         }
  138.         else
  139.             j = next[j];                    //模式串向右移动
  140.         if(j > T.length)                    //匹配成功
  141.             return i - T.length;
  142.         else
  143.             return 0;
  144.     }
  145. }
  147. // //10、插入
  148. // Strlnsert(&S, pos, T) 
  150. // //11、删除
  151. // StrDelete(&S, pos, len)
  153. // //12、销毁
  154. // DestroyString(&S)