串 { 基本概念主串、子串、串长 存储结构 { 定长顺序存储 堆分配存储 块链存储 模式匹配算法 { 暴力匹配法 K M P 算法 { 部分匹配值表 n e x t 数组 n e x t 函数的推理过程 K M P 算法的进一步改进—— n e x t v a l 数组 串\left\{ \begin{array}{l} 基本概念主串、子串、串长\\ 存储结构\left\{ \begin{array}{l} 定长顺序存储\\ 堆分配存储\\ 块链存储 \end{array} \right.\\ 模式匹配算法\left\{ \begin{array}{l} 暴力匹配法\\ KMP算法\left\{ \begin{array}{l} 部分匹配值表\\ next数组\\ next函数的推理过程 \end{array} \right.\\ KMP算法的进一步改进——nextval数组 \end{array} \right. \end{array} \right.串⎩⎨⎧​基本概念主串、子串、串长存储结构⎩⎨⎧​定长顺序存储堆分配存储块链存储​模式匹配算法⎩⎨⎧​暴力匹配法KMP算法⎩⎨⎧​部分匹配值表next数组next函数的推理过程​KMP算法的进一步改进——nextval数组​​文章目录4.1 串的定义和实现4.2 串的模式匹配4.3 例题例一 【模板】KMP例二 Stop Gaming参考文献4.1 串的定义和实现定长顺序存储表示#defineMAXLEN255// 预定义最大串长为255typedefstruct{charch[MAXLEN];// 每一个分量存储一个字符intlength;// 串的实际长度}SString;堆分配存储表示typedefstruct{char*ch;// 按串长分配存储区ch指向串的基地址intlength;// 串的长度}HString;4.2 串的模式匹配求解 next 数组voidget_next(SString T,intnext[]){inti1,j0;next[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i,j;if(T.ch[i]!T.ch[j])next[i]j;elsenext[i]next[j];}elsejnext[j];// 若则令j next[j]循环继续}}定位操作intIndex_KMP(SString S,SString T,intnext[]){inti1,j1;while(iS.lengthjT.length){if(j0||S.ch[i]T.ch[j]){i,j;// 继续比较后继字符}elsejnext[j];// 模式串向右滑动}if(jT.length)returni-T.length;// 匹配成功elsereturn0;}4.3 例题例一 【模板】KMPP3375 【模板】KMP - 洛谷#includebits/stdc.husing namespace std;constintN1000010;#defineMAXLEN1000010// 预定义最大串长为255typedefstruct{charch[MAXLEN];// 每一个分量存储一个字符intlength;// 串的实际长度}SString;SString s,t;intne[N];voidget_next(SString T){inti1,j0;ne[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i,j;ne[i]j;// if (T.ch[i] ! T.ch[j]) ne[i] j;// else ne[i] ne[j];}elsejne[j];}}voidIndex_KMP(SString S,SString T){inti1,j1;while(iS.lengthjT.length){if(j0||S.ch[i]T.ch[j]){i,j;}elsejne[j];if(jT.length){couti-T.lengthendl;jne[j];}}}voidsolve(){cins.ch1t.ch1;s.lengthstrlen(s.ch1);t.lengthstrlen(t.ch1);get_next(t);Index_KMP(s,t);for(inti1;it.length;i)coutne[i1]-1 ;coutendl;}intmain(){cin.tie(0);ios::sync_with_stdio(false);solve();return0;}例二 Stop GamingProblem - E2 - Codeforces题目给出了n nn个长度为m mm的初始数组a aa和对应的目标数组b bb所有数组元素均为互不相同的整数。允许进行一种特殊操作选择一个数组下标i ii和一个值x xx。然后对从第i ii个到第n nn个的每个数组依次执行1.将x xx插入到该数组的开头2.将x xx的值更新为该数组的最后一个元素3.移除该数组的最后一个元素。该操作会连锁影响从第i ii个开始的所有后续数组。目标是使用最少的操作次数将初始数组a aa转换为目标数组b bb。对于每个测试用例需要输出最小操作数以及具体的操作序列即每次操作的i ii和x xx。#includebits/stdc.husing namespace std;typedeflonglongll;constintN300000;intn,m;inta[N50],b[N50];intpos[N50];intv[N50];intlen,tot,tp;voiddfs(intx){// 当前行所有原始元素遍历完成,tp赋值为x-1并返回if(v[x]m){tpmin(tp,x-1);return;}// k为处于当前处于数组行末尾的元素(不是原始数组的行末)intkx*m-v[x];v[x];// 若k大于前缀长返回if(klen)return;// 对前缀的第k个元素对应结果位置到前缀的第k1个元素对应结果位置之间的额外元素, 输出操作for(intipos[k1]-1;ipos[k];i--){coutx1 b[i]\n;// 前面任意一行推入一个元素,后面所有行需重新遍历for(intjtp;jx;jmin(j-1,tp))dfs(j);}}voidsolve(){cinnm;for(inti1;in*m;i)cina[i];// len为前缀长度tot为b数组领先前缀的元素个数// len单调不减lentot0;for(inti1,k0;in;i){for(intj1,t;jm;j){cint;b[i*m-mj]t;// pos记录前缀元素对应结果数组的位置if(a[k1]!t)klen;elsepos[k]i*m-mj;// 如果b数组领先前缀的元素个数 前缀所在行剩余元素个数可以更新前缀长度if((m-k%m)%mtot)lenmax(len,k);}lenk;toti*m-len;}pos[len1]n*m1;// tp等于len/m上取整即前缀末尾元素所在行tp(lenm-1)/m;fill(v,vtp5,0);coutn*m-len\n;for(intitp;i0;i--)dfs(i);}intmain(){ios::sync_with_stdio(0);cin.tie(0);intt;cint;while(t--)solve();return0;}【结论加强】如果该题去掉“元素两两不同”的条件则使用KMP即可优化。如下所示。#includebits/stdc.husing namespace std;typedeflonglongll;constintN300000;intn,m;inta[N50],b[N50];intf[N50],pos[N50];intv[N50];intlen,tot,tp;voiddfs(intx){// 当前行所有原始元素遍历完成,tp赋值为x-1并返回if(v[x]m){tpmin(tp,x-1);return;}// k为处于当前处于数组行末尾的元素(不是原始数组的行末)intkx*m-v[x];v[x];// 若k大于前缀长返回if(klen)return;// 对前缀的第k个元素对应结果位置到前缀的第k1个元素对应结果位置之间的额外元素, 输出操作for(intipos[k1]-1;ipos[k];i--){coutx1 b[i]\n;// 前面任意一行推入一个元素,后面所有行需重新遍历for(intjtp;jx;jmin(j-1,tp))dfs(j);}}voidsolve(){cinnm;for(inti1;in*m;i)cina[i];// KMPfor(inti2,j0;in*m;i){while(ja[j1]!a[i])jf[j];f[i](j(a[j1]a[i]));}// len为前缀长度tot为b数组领先前缀的元素个数// len单调不减lentot0;for(inti1,k0;in;i){for(intj1,t;jm;j){cint;b[i*m-mj]t;while(klena[k1]!t)kf[k];kmax(k,len);// pos记录前缀元素对应结果数组的位置if(a[k1]t)pos[k]i*m-mj;// 如果b数组领先前缀的元素个数 前缀所在行剩余元素个数可以更新前缀长度if((m-k%m)%mtot)lenmax(len,k);}lenk;toti*m-len;}pos[len1]n*m1;coutn*m-len\n;// tp等于len/m上取整即前缀末尾元素所在行tp(lenm-1)/m;fill(v,vtp5,0);for(intitp;i0;i--)dfs(i);}intmain(){ios::sync_with_stdio(0);cin.tie(0);intt;cint;while(t--)solve();return0;}参考文献王道论坛. 数据结构考研复习指导. 电子工业出版社, 2027.luogu.com.cn415411-Submission #304166488 - Codeforces