Erlang Example: Find the Maximum Palindrome Length
A palindrome is a string that is equal to its reverse. The problem here is to find the longest part of a given string that is a palindrome. For instance, the answer is 3 for aacbcx, because cbc is a palindrome, and there is no longer instance. The following program is based on the observation that if x>2 is the length of the longest palindrome, then there must also be a palindrome of length x-2 within the same input word.
Further explanation was presented in class.
-module(palindrome). -export([max/1]). palindrome(X) -> X == lists:reverse(X). max(X) -> Odds = genMax(X,1,0,0), Evens = genMax(X,2,0,0), if Odds >= Evens -> Odds; Evens > Odds -> Evens end. genMax(X,Len,Offset,MaxSoFar) -> case Offset+Len>length(X) of true -> MaxSoFar; % can't improve on this false -> Val = examine(X,Len,Offset), case Val>MaxSoFar of true -> NewMax = Val; false -> NewMax = MaxSoFar end, genMax(X,Len,Offset+1,NewMax) end. examine(X,T,Offset) -> % test string X for palindrome of size T % starting at given Offset % idea is to try for a palindrome at given offset, for % length T; if that works, then back up one in the word % X and try again, with T+2 as the length %% following are comments from earlier testing % S = "examine: " ++ X ++ " length=" % ++ integer_to_list(T) ++ " offset=" ++ integer_to_list(Offset), % io:put_chars(S), io:nl(), if T+Offset=<length(X) -> % looks OK to try a substring of length T here NewCandidate = lists:sublist(X,1+Offset,T), Test = palindrome(NewCandidate), if % NOTE: comma below is like "&&" of Java Test, Offset>0 -> % ok, and recursion possible Recurse = examine(X,T+2,Offset-1), if Recurse > 0 -> Recurse; Recurse < 1 -> T end; Test -> T; % ok, but no recursion possible true -> 0 % failed the palindrome test end; T+Offset>length(X) -> 0 end.
In class, we worked out how to make this program concurrent, by making genMax into a process. This was the result:
-module(palindrome). -export([max/1, genMax/4]). palindrome(X) -> X == lists:reverse(X). max(X) -> register(master,self()), spawn(palindrome,genMax,[X,1,0,0]), spawn(palindrome,genMax,[X,2,0,0]), receive A -> true end, receive B -> true end, if A >= B -> A; B > A -> B end. genMax(X,Len,Offset,MaxSoFar) -> % io:format("genmax called with ~w ~w ~w ~w ~n",[X,Len,Offset,MaxSoFar]), case Offset+Len>length(X) of true -> master ! MaxSoFar, true; % can't improve on this false -> Val = examine(X,Len,Offset), case Val>MaxSoFar of true -> NewMax = Val; false -> NewMax = MaxSoFar end, genMax(X,Len,Offset+1,NewMax), true end.
(Above for the concurrent version, I omitted repeating the examine function, since it wasn't changed from the original version.)