KMP算法的几种模板

快来打我* 2022-06-09 01:09 164阅读 0赞

一、寻找子串首次出现的位置

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 ///寻找子串首次出现的位置 
 #include&lt;stdio.h&gt; 
 
 int&nbsp;a[ 
 1000010],&nbsp;b[ 
 10010]; 
 
 int&nbsp;next[ 
 10010]; 
 
 int&nbsp;n,&nbsp;m; 
 
 void&nbsp;getNext() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///求next数组 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///j表示前缀（前缀是固定的），i表示后缀（后缀是相对的） &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i,&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;next[ 
 0]&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(i&nbsp;&lt;&nbsp;m) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(j&nbsp;==&nbsp;- 
 1&nbsp;||&nbsp;b[i]&nbsp;==&nbsp;b[j])&nbsp; 
 ///如果可以匹配，都加一进行下一轮匹配 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next[i]&nbsp;=&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp;j&nbsp;=&nbsp;next[j];&nbsp; 
 ///如果不能匹配，就退回到next[j]; &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 ///返回首次出现的位置 
 int&nbsp;KMP_Index() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i&nbsp;=&nbsp; 
 0,&nbsp;j&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;getNext(); 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(i&nbsp;&lt;&nbsp;n&nbsp;&amp;&amp;&nbsp;j&nbsp;&lt;&nbsp;m) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(j&nbsp;==&nbsp;- 
 1&nbsp;||&nbsp;a[i]&nbsp;==&nbsp;b[j]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp;j&nbsp;=&nbsp;next[j]; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(j&nbsp;==&nbsp;m) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;i&nbsp;-&nbsp;m&nbsp;+&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;- 
 1; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d",&nbsp;&amp;n,&nbsp;&amp;m); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;a[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;m;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;b[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;KMP_Index()); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

二、统计子串出现的个数

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 ///统计子串出现的次数 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 char&nbsp;W[ 
 10010],&nbsp;T[ 
 1000010]; 
 
 int&nbsp;wlen,&nbsp;tlen; 
 
 int&nbsp;next[ 
 10010]; 
 
 void&nbsp;getNext() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i,&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;next[ 
 0]&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(j&nbsp;&lt;&nbsp;wlen) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(j&nbsp;==&nbsp;- 
 1&nbsp;||&nbsp;W[i]&nbsp;==&nbsp;W[j]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next[i]&nbsp;=&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp;j&nbsp;=&nbsp;next[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;KMP_count() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;ans&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i,&nbsp;j&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(wlen&nbsp;==&nbsp; 
 1&nbsp;&amp;&amp;&nbsp;tlen&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(W[ 
 0]&nbsp;==&nbsp;T[ 
 0]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;getNext(); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for(i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;tlen;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(j&nbsp;&gt;&nbsp; 
 0&nbsp;&amp;&amp;&nbsp;T[i]&nbsp;!=&nbsp;W[j]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;next[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(W[j]&nbsp;==&nbsp;T[i]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(j&nbsp;==&nbsp;wlen) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;next[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;ans; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;tcase; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;tcase); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(tcase--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s%s",&nbsp;&amp;W,&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;wlen&nbsp;=&nbsp;strlen(W); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tlen&nbsp;=&nbsp;strlen(T); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;KMP_count()); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

ps：kmp算法的核心就是避免不必要的回溯，那么什么是不必要的呢？问题由模式串决定，不是由目标串决定