[Erlang 학습 노트] Erlang 단순 구현 KMP - 문자열 일치 알고리즘

KMP 알고리즘 의 개념 에 대해 서 는 모두 가 알 고 있 을 것 입 니 다. 구체 적 으로 는 위 키, 연구, 구 글 을 참조 하여 알 수 있 습 니 다.............................................
쓸데없는 말 말고 코드 를 달 아 라.  =。=

%%%-------------------------------------------------------------------
%%% @author lqg <>
%%% @copyright (C) 2012, lqg
%%% @doc
%%%
%%% @end
%%% Created : 26 Jul 2012 by lqg <>
%%%-------------------------------------------------------------------
-module(kmp).

%% API
-export([patch/2]).

-define(Len(X),array:size(X)).
-define(Get(X,Y),array:get(X,Y)).
-define(Same(X,Y),string:equal(X,Y)).
-define(Set(X,Y,Z),array:set(X,Y,Z)).


%%% I,Content    
%%% J，Keyword    
%%% Next，Keyword          
patch(Content,Keyword) ->
    I=0,J=0,
    Next = get_next(Keyword),
    compare(I,J,Content,Keyword,Next).

%%% C，Content
%%% K，Keyword
%%% N，Next
compare(I,J,C,K,N)->
    case I < ?Len(C) of
	true ->
	    case J== -1 of
		true -> I1=I+1,
			J1=J+1,
			compare(I1,J1,C,K,N);
		false ->
		    case ?Same(?Get(I,C),?Get(J,K)) of
			true -> I1=I+1,
				J1=J+1,
				case J1==?Len(K) of
				    true ->
					{true,{I-J,I}};  %%     ,       
				    false ->
					compare(I1,J1,C,K,N)
				end;
			false ->
			    J1=?Get(J,N),
			    compare(I,J1,C,K,N)
		    end
	    end;
	false ->
	    false                                        %%     
    end.

%%% K,Keyword
%%% H J ,Next    ，H<J
%%% N, Next
get_next(K)->
    H=-1,J=0,
    N=array:new(array:size(K)),
    N1=?Set(0,-1,N),
    get_next(K,N1,H,J).

%%% K,Keyword
%%% H J ,Next    ，H<J
%%% N, Next
get_next(K,N,H,J)->
    case J < ?Len(K)-1 of
	true->	    
	    case H ==-1 of
		true -> J1=J+1,
			H1=H+1,
			N1=?Set(J1,H1,N),
			get_next(K,N1,H1,J1);
		false ->
		    case ?Same(?Get(J,K),?Get(H,K)) of
			       true->J1=J+1,
				     H1=H+1,
				     N1=?Set(J1,H1,N),
				     get_next(K,N1,H1,J1);
			       false->
				      H1=?Get(H,N),
				      get_next(K,N,H1,J)
		    end
	    end;
	false ->
	    N
    end.

코드 는 KMP 알고리즘 을 간단하게 실 현 했 지만 Next [] 가 생 성 될 때 너무 많은 메모리 소모 가 발생 할 까 봐 걱정 입 니 다. 바로 N1 =?Set (J1, H1, N) 이 떨 어 졌 지만 erlang 의 작업 장 소 는 메모리 가 아니 라 코드 입 니 다. 아 톰 만 아니면 문제 없습니다...
erlang 함수 에 많이 사용 되 지 않 기 때문에 n 줄 코드 는 하나의 함수 로 대체 할 수 있 습 니 다.
시간 문제 로 인해 저 는 깊이 연구 하지 않 았 습 니 다. 만약 에 어떤 인형 이 또 발견 하면 저 를 불 러 주 셔 도 됩 니 다. 감사합니다!