Golang实现KMP算法

<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg>

代码先放上，具体实现方法和原理下次补。（咕咕咕。。补了你们也不一定会看）
如果哪里有可以优化的话请告诉我，我改进改进。

<pre><code class="lang-go hljs"><span class="token keyword">func</span> <span class="token function">kmp</span><span class="token punctuation">(</span>str1<span class="token punctuation">,</span> str2 <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span> <span class="token comment">// count next_arr</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>str1<span class="token punctuation">)</span><span class="token operator"><</span><span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">}</span> next_arr <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token comment">// 这里一般情况下 i==0时应该是-1，但是为了减少代码，</span> <span class="token comment">// 所以合成0，不影响算法的结果</span> t <span class="token operator">:=</span> <span class="token number">0</span> <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> j<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> str2<span class="token punctuation">[</span><span class="token punctuation">:</span>j<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> str2<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token punctuation">(</span>j<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">:</span>i<span class="token punctuation">]</span> <span class="token punctuation">{</span> t <span class="token operator">=</span> j <span class="token operator"> </span> <span class="token number">1</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> next_arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> t <span class="token punctuation">}</span> <span class="token comment">// 初始化i,y,index 这里应该都看得懂</span> i<span class="token punctuation">,</span> y<span class="token punctuation">,</span> index <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token comment">// 这里就是开始kmp算法了,针对自己的习惯,对其进行了小部分改造</span> <span class="token keyword">for</span> i <span class="token operator"><=</span> <span class="token function">len</span><span class="token punctuation">(</span>str1<span class="token punctuation">)</span><span class="token operator">-</span><span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> j <span class="token operator">:=</span> y<span class="token punctuation">;</span> j <span class="token operator"><=</span> <span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> j <span class="token operator">==</span> <span class="token function">len</span><span class="token punctuation">(</span>str2<span class="token punctuation">)</span> <span class="token punctuation">{</span> index <span class="token operator">=</span> i i<span class="token operator"> </span> y <span class="token operator">=</span> <span class="token number">0</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> str1<span class="token punctuation">[</span>i<span class="token operator"> </span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> str2<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> next_arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator"><</span> <span class="token number">1</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> j <span class="token operator">