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">></span> <span class="token number">1</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> i <span class="token operator">=</span> i <span class="token operator"> </span> <span class="token punctuation">(</span>j <span class="token operator">-</span> next_arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> y <span class="token operator">=</span> next_arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token keyword">break</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 number">1</span> <span class="token punctuation">{</span> i<span class="token operator"> </span> y <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">}</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> i <span class="token operator">=</span> i <span class="token operator"> </span> <span class="token punctuation">(</span>j <span class="token operator">-</span> next_arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> y <span class="token operator">=</span> next_arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> index <span class="token punctuation">}</span> </code></pre> 到此这篇关于“Golang实现KMP算法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
php中字符串匹配KMP算法实现例子
数据结构与算法JavaScript (五) 串(经典KMP算法)
KMP串中的模式匹配算法及从next[]到nextVal[]
用C 与Java代码实现KMP算法实例
Golang实现KMP算法
三种字符串查找算法的Go实现
golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
数据结构与算法JavaScript (四) 串(BF)
Go实战--golang中各种排序算法实现以及生成随机数