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

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

?

?

首先是KMP 介绍:

%% @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> 

?