解题报告 (六) KMP

文章目录

一、KMP 算法讲解夜深人静写算法（KMP） 二、KMP 解题报告HDU 1711 Number SequenceHDU 2087 剪花布条PKU 3461 OulipoHDU 2203 亲和串HDU 1238 SubstringsHDU 2328 Corporate IdentityHDU 2594 Simpsons’ Hidden TalentsPKU 2406 Power StringsHDU 1358 PeriodHDU 3336 Count the stringHDU 4300 Clairewd’s messagePKU 2752 Seek the Name, Seek the FameHDU 4763 Theme SectionPKU 3690 ConstellationsHDU 3746 Cyclic NacklaceHDU 5918 Sequence I

一、KMP 算法讲解

夜深人静写算法（KMP）

二、KMP 解题报告

HDU 1711 Number Sequence

链接：HDU 1711 Number Sequence题意：求一个整数串在另一个整数串中第一次出现的位置，找不到输出 -1；难度：★☆☆☆☆题解：KMP 模板题，核心逻辑是 KMP 匹配到匹配串结尾时通过匹配串长度算出目标串起始位置； if (MPos == MLen - 1) { return TPos - (MLen - 1) + 1; // 下标从1开始，所以+1 }

HDU 2087 剪花布条

链接：HDU 2087 剪花布条题意：求一个 目标串 里面有多少个不重叠的 匹配串；难度：★☆☆☆☆题解：KMP 模板题，核心逻辑是 KMP 匹配到匹配串结尾时从 NULL_MATCH 开始重新匹配； if (MPos == MLen - 1) { MPos = NULL_MATCH; ++ans; }

PKU 3461 Oulipo

链接：PKU 3461 Oulipo题意：求一个 目标串 里面有多少个可重叠的 匹配串；难度：★☆☆☆☆题解：KMP 模板题，核心逻辑是 KMP 匹配到匹配串结尾时从 next[MPos] 开始重新匹配； if (MPos == MLen - 1) { MPos = next[MPos]; ++ans; }

HDU 2203 亲和串

链接：HDU 2203 亲和串题意：问 匹配串 能否在 目标串 进行循环移位后找到；难度：★☆☆☆☆题解：将目标串拷贝一份套用KMP即可，需要注意的是，如果 匹配串 长度 大于 目标串 需要预判，这种情况一定是找不到的；

HDU 1238 Substrings

链接：HDU 1238 Substrings题意：给定一系列字符串，找到一个最长的子串，满足它（或者它的逆序串）是所有字符串的子串；难度：★☆☆☆☆题解：暴力枚举长度，从长到短枚举所有的字符串的子串，分别做 KMP 匹配即可，找到一个立即返回；

HDU 2328 Corporate Identity

链接：HDU 2328 Corporate Identity难度：★☆☆☆☆题解：类似 HDU 1238 Substrings 暴力找子串，再用 KMP 匹配；

HDU 2594 Simpsons’ Hidden Talents

链接：Simpsons’ Hidden Talents题意：给定两个字符串 A 和 B，求一个既是A的前缀，又是B的后缀的子串，并且保证这个串最长；难度：★☆☆☆☆题解：将两个字符串收尾拼接后，用一个未出现过的字符拼接，求一次 next 数组即可；

PKU 2406 Power Strings

链接：PKU 2406 Power Strings题意：如果一个串 A 可以表示成 X^K （X为多个字符的集合，K > 1）的形式，则称 A 为 叠串；给定一个字符串，输出最大的 K；难度：★★☆☆☆题解：参见 夜深人静写算法（KMP） 对于 叠串 的讲解；

HDU 1358 Period

链接：HDU 1358 Period题意：给定一个字符串，要求出字符串的所有前缀中能够表示成 A^K 的形式的前缀，并且保证 K > 1 ，而且 K 尽量大，输出所有的 前缀长度 和 对应的 K；难度：★★☆☆☆题解： i01234567M[i]aasaaasanext[i]-10-101123i - next[i]11333444 首先来看 K = 2 的情况，那么一定满足： i - next[i] == next[i] - (-1); 再来看 K = 3 的情况，同理可得： i - next[i] == next[i] - next[ next[i] ] == next[ next[i] ] - (-1); 继续归纳 K = 4,5，6… 的情况，可以得出，只要 i - next[i] 能够被 next[i] - (-1) 整除，那么这个除出来的商就是再加上 1 就是所求的 K 了；所以第 i 个位置的 K_i 的值 = (next[i] - (-1)) / (i - next[i]) + 1；

HDU 3336 Count the string

链接：HDU 3336 Count the string题意：给定一个字符串，要求求出它所有的前缀在这个字符串出现次数的和，模上 10007；难度：★★☆☆☆题解：拿 “ababab” 举例，如下： i012345sabababnext[i]-1-10123a+1+1+1ab+1+1+1aba+1+1abab+1+1ababa+1abababa+1 图中的 +1 代表了 以当前位置结尾的后缀为对应的前缀贡献了几次匹配；以第 i 个字符结尾的字符串中必定有一个 next[i] 的前缀，即 第 next[i] 的位置为 i 位置贡献 1，画出 next 图就是： #mermaid-svg-YSvGYufPo1CbxNeu .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-YSvGYufPo1CbxNeu .label text{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .node rect,#mermaid-svg-YSvGYufPo1CbxNeu .node circle,#mermaid-svg-YSvGYufPo1CbxNeu .node ellipse,#mermaid-svg-YSvGYufPo1CbxNeu .node polygon,#mermaid-svg-YSvGYufPo1CbxNeu .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-YSvGYufPo1CbxNeu .node .label{text-align:center;fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .node.clickable{cursor:pointer}#mermaid-svg-YSvGYufPo1CbxNeu .arrowheadPath{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-YSvGYufPo1CbxNeu .flowchart-link{stroke:#333;fill:none}#mermaid-svg-YSvGYufPo1CbxNeu .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-YSvGYufPo1CbxNeu .edgeLabel rect{opacity:0.9}#mermaid-svg-YSvGYufPo1CbxNeu .edgeLabel span{color:#333}#mermaid-svg-YSvGYufPo1CbxNeu .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-YSvGYufPo1CbxNeu .cluster text{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-YSvGYufPo1CbxNeu .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-YSvGYufPo1CbxNeu text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-YSvGYufPo1CbxNeu .actor-line{stroke:grey}#mermaid-svg-YSvGYufPo1CbxNeu .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-YSvGYufPo1CbxNeu .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-YSvGYufPo1CbxNeu #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-YSvGYufPo1CbxNeu .sequenceNumber{fill:#fff}#mermaid-svg-YSvGYufPo1CbxNeu #sequencenumber{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu #crosshead path{fill:#333;stroke:#333}#mermaid-svg-YSvGYufPo1CbxNeu .messageText{fill:#333;stroke:#333}#mermaid-svg-YSvGYufPo1CbxNeu .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-YSvGYufPo1CbxNeu .labelText,#mermaid-svg-YSvGYufPo1CbxNeu .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-YSvGYufPo1CbxNeu .loopText,#mermaid-svg-YSvGYufPo1CbxNeu .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-YSvGYufPo1CbxNeu .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-YSvGYufPo1CbxNeu .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-YSvGYufPo1CbxNeu .noteText,#mermaid-svg-YSvGYufPo1CbxNeu .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-YSvGYufPo1CbxNeu .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSvGYufPo1CbxNeu .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSvGYufPo1CbxNeu .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-YSvGYufPo1CbxNeu .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .section{stroke:none;opacity:0.2}#mermaid-svg-YSvGYufPo1CbxNeu .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-YSvGYufPo1CbxNeu .section2{fill:#fff400}#mermaid-svg-YSvGYufPo1CbxNeu .section1,#mermaid-svg-YSvGYufPo1CbxNeu .section3{fill:#fff;opacity:0.2}#mermaid-svg-YSvGYufPo1CbxNeu .sectionTitle0{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .sectionTitle1{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .sectionTitle2{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .sectionTitle3{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-YSvGYufPo1CbxNeu .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .grid path{stroke-width:0}#mermaid-svg-YSvGYufPo1CbxNeu .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-YSvGYufPo1CbxNeu .task{stroke-width:2}#mermaid-svg-YSvGYufPo1CbxNeu .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .taskText:not([font-size]){font-size:11px}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-YSvGYufPo1CbxNeu .task.clickable{cursor:pointer}#mermaid-svg-YSvGYufPo1CbxNeu .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-YSvGYufPo1CbxNeu .taskText0,#mermaid-svg-YSvGYufPo1CbxNeu .taskText1,#mermaid-svg-YSvGYufPo1CbxNeu .taskText2,#mermaid-svg-YSvGYufPo1CbxNeu .taskText3{fill:#fff}#mermaid-svg-YSvGYufPo1CbxNeu .task0,#mermaid-svg-YSvGYufPo1CbxNeu .task1,#mermaid-svg-YSvGYufPo1CbxNeu .task2,#mermaid-svg-YSvGYufPo1CbxNeu .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutside0,#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutside2{fill:#000}#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutside1,#mermaid-svg-YSvGYufPo1CbxNeu .taskTextOutside3{fill:#000}#mermaid-svg-YSvGYufPo1CbxNeu .active0,#mermaid-svg-YSvGYufPo1CbxNeu .active1,#mermaid-svg-YSvGYufPo1CbxNeu .active2,#mermaid-svg-YSvGYufPo1CbxNeu .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-YSvGYufPo1CbxNeu .activeText0,#mermaid-svg-YSvGYufPo1CbxNeu .activeText1,#mermaid-svg-YSvGYufPo1CbxNeu .activeText2,#mermaid-svg-YSvGYufPo1CbxNeu .activeText3{fill:#000 !important}#mermaid-svg-YSvGYufPo1CbxNeu .done0,#mermaid-svg-YSvGYufPo1CbxNeu .done1,#mermaid-svg-YSvGYufPo1CbxNeu .done2,#mermaid-svg-YSvGYufPo1CbxNeu .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-YSvGYufPo1CbxNeu .doneText0,#mermaid-svg-YSvGYufPo1CbxNeu .doneText1,#mermaid-svg-YSvGYufPo1CbxNeu .doneText2,#mermaid-svg-YSvGYufPo1CbxNeu .doneText3{fill:#000 !important}#mermaid-svg-YSvGYufPo1CbxNeu .crit0,#mermaid-svg-YSvGYufPo1CbxNeu .crit1,#mermaid-svg-YSvGYufPo1CbxNeu .crit2,#mermaid-svg-YSvGYufPo1CbxNeu .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-YSvGYufPo1CbxNeu .activeCrit0,#mermaid-svg-YSvGYufPo1CbxNeu .activeCrit1,#mermaid-svg-YSvGYufPo1CbxNeu .activeCrit2,#mermaid-svg-YSvGYufPo1CbxNeu .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-YSvGYufPo1CbxNeu .doneCrit0,#mermaid-svg-YSvGYufPo1CbxNeu .doneCrit1,#mermaid-svg-YSvGYufPo1CbxNeu .doneCrit2,#mermaid-svg-YSvGYufPo1CbxNeu .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-YSvGYufPo1CbxNeu .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-YSvGYufPo1CbxNeu .milestoneText{font-style:italic}#mermaid-svg-YSvGYufPo1CbxNeu .doneCritText0,#mermaid-svg-YSvGYufPo1CbxNeu .doneCritText1,#mermaid-svg-YSvGYufPo1CbxNeu .doneCritText2,#mermaid-svg-YSvGYufPo1CbxNeu .doneCritText3{fill:#000 !important}#mermaid-svg-YSvGYufPo1CbxNeu .activeCritText0,#mermaid-svg-YSvGYufPo1CbxNeu .activeCritText1,#mermaid-svg-YSvGYufPo1CbxNeu .activeCritText2,#mermaid-svg-YSvGYufPo1CbxNeu .activeCritText3{fill:#000 !important}#mermaid-svg-YSvGYufPo1CbxNeu .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-YSvGYufPo1CbxNeu g.classGroup text .title{font-weight:bolder}#mermaid-svg-YSvGYufPo1CbxNeu g.clickable{cursor:pointer}#mermaid-svg-YSvGYufPo1CbxNeu g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-YSvGYufPo1CbxNeu g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-YSvGYufPo1CbxNeu .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-YSvGYufPo1CbxNeu .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-YSvGYufPo1CbxNeu .dashed-line{stroke-dasharray:3}#mermaid-svg-YSvGYufPo1CbxNeu #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu .commit-id,#mermaid-svg-YSvGYufPo1CbxNeu .commit-msg,#mermaid-svg-YSvGYufPo1CbxNeu .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-YSvGYufPo1CbxNeu g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-YSvGYufPo1CbxNeu g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-YSvGYufPo1CbxNeu g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-YSvGYufPo1CbxNeu .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-YSvGYufPo1CbxNeu .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-YSvGYufPo1CbxNeu .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-YSvGYufPo1CbxNeu .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-YSvGYufPo1CbxNeu .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-YSvGYufPo1CbxNeu .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-YSvGYufPo1CbxNeu .edgeLabel text{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-YSvGYufPo1CbxNeu .node circle.state-start{fill:black;stroke:black}#mermaid-svg-YSvGYufPo1CbxNeu .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-YSvGYufPo1CbxNeu #statediagram-barbEnd{fill:#9370db}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-state .divider{stroke:#9370db}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-YSvGYufPo1CbxNeu .note-edge{stroke-dasharray:5}#mermaid-svg-YSvGYufPo1CbxNeu .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-YSvGYufPo1CbxNeu .error-icon{fill:#522}#mermaid-svg-YSvGYufPo1CbxNeu .error-text{fill:#522;stroke:#522}#mermaid-svg-YSvGYufPo1CbxNeu .edge-thickness-normal{stroke-width:2px}#mermaid-svg-YSvGYufPo1CbxNeu .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-YSvGYufPo1CbxNeu .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-YSvGYufPo1CbxNeu .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-YSvGYufPo1CbxNeu .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-YSvGYufPo1CbxNeu .marker{fill:#333}#mermaid-svg-YSvGYufPo1CbxNeu .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-YSvGYufPo1CbxNeu { color: rgba(0, 0, 0, 0.75); font: ; } +1 +1 +1 +1 +1 +1 0 1 2 3 4 5 -1 所以可以列出状态转移方程： $$dp[i]=\{\begin{array}{llc}1& & next[i]==-1\\ dp[next[i]]+1& & next[i]<>-1\end{array}$$

HDU 4300 Clairewd’s message

链接：HDU 4300 Clairewd’s message题意：给出一个密文转换表，再给出一个串，串包含所有的密文和部分的明文，求最短的可能的包含密文和明文的完整串；难度：★★★☆☆题解：对整个串利用密文转换表进行解密操作，然后把 加密串作为 目标串 T，解密串作为 匹配串 M 计算一次 KMP，需要注意的是，给出的串包含全部的密文和部分的明文，所以至少密文的部分占总长度的一半以上；所以匹配的时候要从 (Len+1)/2 的位置开始匹配；当 KMP 匹配到结尾，最后得到的M[ 0 … MPos ] 就是 密文的开头 和 明文的结尾，输出的时候进行一下处理即可；

PKU 2752 Seek the Name, Seek the Fame

链接：PKU 2752 Seek the Name, Seek the Fame题意：输出所有给定串的 前后缀 的长度；难度：★★★☆☆题解：对整个字符串求一遍 next 数组，然后从结尾字符往前一直求 next 并且记录输出即可；例如，对于字符串 “ababcababababcabab” ，可以画出 next 图如下： #mermaid-svg-K9FPS6iFFxp2QWkY .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .label text{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .node rect,#mermaid-svg-K9FPS6iFFxp2QWkY .node circle,#mermaid-svg-K9FPS6iFFxp2QWkY .node ellipse,#mermaid-svg-K9FPS6iFFxp2QWkY .node polygon,#mermaid-svg-K9FPS6iFFxp2QWkY .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-K9FPS6iFFxp2QWkY .node .label{text-align:center;fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .node.clickable{cursor:pointer}#mermaid-svg-K9FPS6iFFxp2QWkY .arrowheadPath{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-K9FPS6iFFxp2QWkY .flowchart-link{stroke:#333;fill:none}#mermaid-svg-K9FPS6iFFxp2QWkY .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-K9FPS6iFFxp2QWkY .edgeLabel rect{opacity:0.9}#mermaid-svg-K9FPS6iFFxp2QWkY .edgeLabel span{color:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-K9FPS6iFFxp2QWkY .cluster text{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-K9FPS6iFFxp2QWkY .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-K9FPS6iFFxp2QWkY text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-K9FPS6iFFxp2QWkY .actor-line{stroke:grey}#mermaid-svg-K9FPS6iFFxp2QWkY .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-K9FPS6iFFxp2QWkY #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .sequenceNumber{fill:#fff}#mermaid-svg-K9FPS6iFFxp2QWkY #sequencenumber{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY #crosshead path{fill:#333;stroke:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .messageText{fill:#333;stroke:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-K9FPS6iFFxp2QWkY .labelText,#mermaid-svg-K9FPS6iFFxp2QWkY .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-K9FPS6iFFxp2QWkY .loopText,#mermaid-svg-K9FPS6iFFxp2QWkY .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-K9FPS6iFFxp2QWkY .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-K9FPS6iFFxp2QWkY .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-K9FPS6iFFxp2QWkY .noteText,#mermaid-svg-K9FPS6iFFxp2QWkY .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-K9FPS6iFFxp2QWkY .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-K9FPS6iFFxp2QWkY .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-K9FPS6iFFxp2QWkY .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-K9FPS6iFFxp2QWkY .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .section{stroke:none;opacity:0.2}#mermaid-svg-K9FPS6iFFxp2QWkY .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-K9FPS6iFFxp2QWkY .section2{fill:#fff400}#mermaid-svg-K9FPS6iFFxp2QWkY .section1,#mermaid-svg-K9FPS6iFFxp2QWkY .section3{fill:#fff;opacity:0.2}#mermaid-svg-K9FPS6iFFxp2QWkY .sectionTitle0{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .sectionTitle1{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .sectionTitle2{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .sectionTitle3{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-K9FPS6iFFxp2QWkY .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .grid path{stroke-width:0}#mermaid-svg-K9FPS6iFFxp2QWkY .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-K9FPS6iFFxp2QWkY .task{stroke-width:2}#mermaid-svg-K9FPS6iFFxp2QWkY .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .taskText:not([font-size]){font-size:11px}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-K9FPS6iFFxp2QWkY .task.clickable{cursor:pointer}#mermaid-svg-K9FPS6iFFxp2QWkY .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-K9FPS6iFFxp2QWkY .taskText0,#mermaid-svg-K9FPS6iFFxp2QWkY .taskText1,#mermaid-svg-K9FPS6iFFxp2QWkY .taskText2,#mermaid-svg-K9FPS6iFFxp2QWkY .taskText3{fill:#fff}#mermaid-svg-K9FPS6iFFxp2QWkY .task0,#mermaid-svg-K9FPS6iFFxp2QWkY .task1,#mermaid-svg-K9FPS6iFFxp2QWkY .task2,#mermaid-svg-K9FPS6iFFxp2QWkY .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutside0,#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutside2{fill:#000}#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutside1,#mermaid-svg-K9FPS6iFFxp2QWkY .taskTextOutside3{fill:#000}#mermaid-svg-K9FPS6iFFxp2QWkY .active0,#mermaid-svg-K9FPS6iFFxp2QWkY .active1,#mermaid-svg-K9FPS6iFFxp2QWkY .active2,#mermaid-svg-K9FPS6iFFxp2QWkY .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-K9FPS6iFFxp2QWkY .activeText0,#mermaid-svg-K9FPS6iFFxp2QWkY .activeText1,#mermaid-svg-K9FPS6iFFxp2QWkY .activeText2,#mermaid-svg-K9FPS6iFFxp2QWkY .activeText3{fill:#000 !important}#mermaid-svg-K9FPS6iFFxp2QWkY .done0,#mermaid-svg-K9FPS6iFFxp2QWkY .done1,#mermaid-svg-K9FPS6iFFxp2QWkY .done2,#mermaid-svg-K9FPS6iFFxp2QWkY .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-K9FPS6iFFxp2QWkY .doneText0,#mermaid-svg-K9FPS6iFFxp2QWkY .doneText1,#mermaid-svg-K9FPS6iFFxp2QWkY .doneText2,#mermaid-svg-K9FPS6iFFxp2QWkY .doneText3{fill:#000 !important}#mermaid-svg-K9FPS6iFFxp2QWkY .crit0,#mermaid-svg-K9FPS6iFFxp2QWkY .crit1,#mermaid-svg-K9FPS6iFFxp2QWkY .crit2,#mermaid-svg-K9FPS6iFFxp2QWkY .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-K9FPS6iFFxp2QWkY .activeCrit0,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCrit1,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCrit2,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-K9FPS6iFFxp2QWkY .doneCrit0,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCrit1,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCrit2,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-K9FPS6iFFxp2QWkY .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-K9FPS6iFFxp2QWkY .milestoneText{font-style:italic}#mermaid-svg-K9FPS6iFFxp2QWkY .doneCritText0,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCritText1,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCritText2,#mermaid-svg-K9FPS6iFFxp2QWkY .doneCritText3{fill:#000 !important}#mermaid-svg-K9FPS6iFFxp2QWkY .activeCritText0,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCritText1,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCritText2,#mermaid-svg-K9FPS6iFFxp2QWkY .activeCritText3{fill:#000 !important}#mermaid-svg-K9FPS6iFFxp2QWkY .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-K9FPS6iFFxp2QWkY g.classGroup text .title{font-weight:bolder}#mermaid-svg-K9FPS6iFFxp2QWkY g.clickable{cursor:pointer}#mermaid-svg-K9FPS6iFFxp2QWkY g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-K9FPS6iFFxp2QWkY g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-K9FPS6iFFxp2QWkY .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-K9FPS6iFFxp2QWkY .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-K9FPS6iFFxp2QWkY .dashed-line{stroke-dasharray:3}#mermaid-svg-K9FPS6iFFxp2QWkY #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY .commit-id,#mermaid-svg-K9FPS6iFFxp2QWkY .commit-msg,#mermaid-svg-K9FPS6iFFxp2QWkY .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-K9FPS6iFFxp2QWkY g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-K9FPS6iFFxp2QWkY g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-K9FPS6iFFxp2QWkY g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-K9FPS6iFFxp2QWkY .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-K9FPS6iFFxp2QWkY .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-K9FPS6iFFxp2QWkY .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-K9FPS6iFFxp2QWkY .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-K9FPS6iFFxp2QWkY .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-K9FPS6iFFxp2QWkY .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-K9FPS6iFFxp2QWkY .edgeLabel text{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-K9FPS6iFFxp2QWkY .node circle.state-start{fill:black;stroke:black}#mermaid-svg-K9FPS6iFFxp2QWkY .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-K9FPS6iFFxp2QWkY #statediagram-barbEnd{fill:#9370db}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-state .divider{stroke:#9370db}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-K9FPS6iFFxp2QWkY .note-edge{stroke-dasharray:5}#mermaid-svg-K9FPS6iFFxp2QWkY .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-K9FPS6iFFxp2QWkY .error-icon{fill:#522}#mermaid-svg-K9FPS6iFFxp2QWkY .error-text{fill:#522;stroke:#522}#mermaid-svg-K9FPS6iFFxp2QWkY .edge-thickness-normal{stroke-width:2px}#mermaid-svg-K9FPS6iFFxp2QWkY .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-K9FPS6iFFxp2QWkY .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-K9FPS6iFFxp2QWkY .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-K9FPS6iFFxp2QWkY .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-K9FPS6iFFxp2QWkY .marker{fill:#333}#mermaid-svg-K9FPS6iFFxp2QWkY .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-K9FPS6iFFxp2QWkY { color: rgba(0, 0, 0, 0.75); font: ; } 1 3 8 17 -1 所以输出为 2 4 8 18 （输出的是长度，需要 next[i] + 1）；

HDU 4763 Theme Section

链接：HDU 4763 Theme Section题意：给定一个长度为N(1 <= N <= 10⁶)的字符串S，问能否和模式串 EAEBE 进行匹配其中A和B表示任意随机字符，如果能匹配，输出E的最大可能长度，不能匹配输出0。难度：★★★☆☆ 题解：PKU 2752 的加强版；首先通过 next 数组，求出所有有可能产生 前后缀 的位置，然后在中间剩余的子串中匹配前缀；假设当前枚举长度为 i，那么在S[i … N-1-i] 中如果能够找到一个长度为 i 的子串满足和 S[0…i-1] 完全匹配，那么 i 就是一个可行解，又因为枚举是从大到小进行的，所以 i 就是E可能的最大长度。于是问题就转变成了判断 S[i … N - 1 - i] 中是否存在一个和 S[0…i-1] 完全匹配的子串。如果存在，那么必定存在一个$$k(2\ast i-1<=k<=N-1-i)$$，使得$$S[k-i+1...k]==S[0...i-1]$$，所以必定有$$Next[Next[...[k]]]==i-1$$，所以我们可以预先将S[i … N-1-i]区间内所有的Next值退化后进行Hash，然后在枚举某个长度i的时候去Hash数组中找i是否被标记，如果被标记说明存在某个k满足$$S[k-i+1...k]==S[0...i-1]$$，i 就是最大可能长度。

PKU 3690 Constellations

链接：PKU 3690 Constellations题意：给定 N * M (N <= 1000, M <= 1000) 的01矩阵S，再给定T(T <= 100) 个 P * Q (P <= 50, Q <= 50) 的01矩阵，问P*Q的矩阵中有多少个是S的子矩阵。难度：★★★☆☆题解：由于P <= 50，所以我们可以把所有 P * Q 的矩阵进行二进制位压缩，将 P * Q 的矩阵的每一列压缩成一个64位整数，这样 P * Q 的矩阵就变成了一个长度为Q的整数序列T，用同样的方式对 N * M 的矩阵进行压缩，总共可以产生 (N-P+1) 个长度为M的整数序列，剩下的就是进行最多 (N-P+1) 次KMP匹配了。

HDU 3746 Cyclic Nacklace

链接：HDU 3746 Cyclic Nacklace题意：给定一个长度为 N (N <= 10⁵) 的字符串S，求在它的末尾添加几个字符使得他变成一个至少重复两次的连续重复串，要求添加的字符数最少。难度：★★★☆☆题解：将字符串当成是 X…XY 的形式来，其中 X 字符串的长度大于Y，Y 字符串的长度可能为 0；然后枚举的是 X 字符串的长度 XLen；可以得到一些数据： $$X重复的次数K=floor(MLen/XLen)$$ $$Y的长度YLen=MLen-XLen\ast K$$ 然后根据叠串公式判断前缀 $$S[0...XLen\ast K-1]$$ 是否是一个 X 的叠串；如果是，判断剩余的 Y 字符串是否为 X 的前缀，这一步可以通过预处理 next 数组来做；最后计算一个最小的 XLen - YLen 就是答案；

HDU 5918 Sequence I

链接：HDU 5918 Sequence I题意：有两个整数数列，数列a为：$a[0],a[1]...a[n-1]$； 数列b为 $b[0],b[1]...b[m-1]$；给定一个数字 p，期望能够找到 q，满足数列 $b=a[q],a[q+p]...a[q+(m-1)p]$，求这样的 q 的数量；难度：★★★☆☆题解：将数列 a 拆成 p 个数列，然后分别和 b 进行KMP，结果累加；这里提供几组数据： 10 10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 5 2 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 10 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 6 3 1 1 2 3 1 2 3 1 2 3 6 3 2 1 3 2 2 3 1 1 2 3 5 3 2 1 3 2 2 3 1 2 3 8 2 2 1 1 3 3 1 1 3 3 1 3