[练习]erlang算法练习--KMP

生活有点无聊,就用erlang写写一些算法吧.闲着也闲着

 

 

首先是KMP 介绍:

http://zh.wikipedia.org/wiki/%E5%85%8B%E5%8A%AA%E6%96%AF-%E8%8E%AB%E9%87%8C%E6%96%AF-%E6%99%AE%E6%8B%89%E7%89%B9%E7%AE%97%E6%B3%95

 关于字符串匹配的 原理蛮简单的:

 被匹配字符串MWord 匹配字符串SWord M表示MWord的下标 S表示SWord的下标

 1，初始化M=1，

 2，如果M大于MWord的长度，返回没找到。如果lists:nth(M, MWord) == lists:nth(1, SWord) 那么继续搜索到3 否则M+1 继续2

 3，如果匹配 返回{found,begin,length} 如果没有匹配M+1返回 2.

代码也很简单:(erlang中lists:nth/1是从下标1开始的)

%% @author cc fairjm
%% @doc @todo kmp算法实现.


-module(kmp).

%% ====================================================================
%% API functions
%% ====================================================================
-export([find/2]).



%% ====================================================================
%% Internal functions
%% ====================================================================

find(MWord,SWord) when is_list(MWord),is_list(SWord) ->
  search(MWord, SWord,1)  
.
  
search(MWord,SWord,M) when M=<length(MWord)->
  %TempM=M,
  case lists:nth(M, MWord) == lists:nth(1, SWord) of
	  true  -> 
		  case doSearch(MWord, SWord, M+1, 2) of 
			  {not_found} ->search(MWord, SWord, M+1);
			  Found -> Found
		  end;
	  false -> search(MWord, SWord,M+1)
  end;

search(MWord,SWord,M) ->
	{not_found}.

doSearch(MWord,SWord,M,I) when I==length(SWord)+1 ->
	{found,M-I+1,I-1}
;

doSearch(MWord,SWord,M,I) when M>length(MWord) ->
   {not_found};

doSearch(MWord,SWord,M,I) ->
   case lists:nth(M, MWord)==lists:nth(I, SWord) of
        false -> {not_found};
        true -> doSearch(MWord, SWord, M+1, I+1)
   end.
	

 没有高亮不太舒服 放章截图吧:

 

测试:

Eshell V5.10.2
(a@dell-PC)1> kmp:find("vvvvvvvvv", "c").
{not_found}
(a@dell-PC)2> kmp:find("vvvvvvvvv", "v").
{found,1,1}
(a@dell-PC)3> kmp:find("avcvc", "cv").
{found,3,2}
(a@dell-PC)4> kmp:find("ABC ABCDAB ABCDABCDABDE", "ABCDABD").
{found,16,7}
(a@dell-PC)5>