讨论KMP.2 如何修改 KMP 函数，使其与 strstr 有一致的接口？

<p>要让 KMP 函数返回模式在文本中的子串，可以修改函数的返回类型为字符串类型。同时，在 KMP 函数内部要记录子串在文本中的起始和终止下标，然后返回这个子串。下面是一个简单的修改版本：</p><p><br ></p><p><br ></p><p>#include &lt;iostream&gt;</p><p>#include &lt;cstring&gt;</p><p>using namespace std;</p><p><br ></p><p>string KMP(string text, string pattern)</p><p>{</p><p>&nbsp; &nbsp; int tlen = text.size();</p><p>&nbsp; &nbsp; int plen = pattern.size();</p><p>&nbsp; &nbsp; int fail[plen + 1];</p><p>&nbsp; &nbsp; memset(fail, -1, sizeof(fail));</p><p><br ></p><p>&nbsp; &nbsp; for (int j = 1; j &lt; plen; ++j) {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; int i = fail[j - 1];</p><p>&nbsp; &nbsp; &nbsp; &nbsp; while (pattern[j] != pattern[i + 1] &amp;&amp; i &gt;= 0) i = fail[i];</p><p>&nbsp; &nbsp; &nbsp; &nbsp; if (pattern[j] == pattern[i + 1]) fail[j] = i + 1;</p><p>&nbsp; &nbsp; }</p><p><br ></p><p>&nbsp; &nbsp; int i = 0, j = 0;</p><p>&nbsp; &nbsp; while (i &lt; tlen &amp;&amp; j &lt; plen) {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; if (text[i] == pattern[j]) {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++i; ++j;</p><p>&nbsp; &nbsp; &nbsp; &nbsp; } else if (j == 0) {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++i;</p><p>&nbsp; &nbsp; &nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = fail[j - 1] + 1;</p><p>&nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; }</p><p><br ></p><p>&nbsp; &nbsp; if (j == plen) {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return text.substr(i - plen, plen);</p><p>&nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return &quot;not found&quot;;</p><p>&nbsp; &nbsp; }</p><p>}</p><p><br ></p><p>int main()</p><p>{</p><p>&nbsp; &nbsp; string text = &quot;ABCABCABCABD&quot;;</p><p>&nbsp; &nbsp; string pattern = &quot;ABCABD&quot;;</p><p>&nbsp; &nbsp; cout &lt;&lt; KMP(text, pattern) &lt;&lt; endl; // output: ABCABD</p><p>&nbsp; &nbsp; return 0;</p><p>}</p><p><br ></p><p>在 main 函数里，我们用 cout 输出 KMP 函数返回的字符串。这样，就可以在调用 KMP 函数后方便地输出子串了。</p><p><br ></p>

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！

嗯...

嗯...

1

1

1

1

1

1

1

1

1

1

1

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！

通过学习该门课程，我学习到了很多有关于该门课程的知识，很大程度上提升的我对该领域的兴趣，加强了课外兴趣，培养了创新能力，学到了很多知识，收获颇多！！！！