pinocchio

Maximal palindrome in erlang

Jan 5th, 2012
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Erlang 3.13 KB | None | 0 0
  1. -module (palindrome).
  2. -compile ([export_all]).
  3.  
  4. maximal_palindrome_in (String) ->
  5.     Stack = [],
  6.     Largest = [],    
  7.     no_center_found (String, Stack, Largest).
  8.  
  9. no_center_found (_RemainingInput = [], _Stack, Largest) -> Largest;    
  10.  
  11. no_center_found ([NextChar|RestOfInput], [NextChar|RestOfStack], Largest) ->
  12.     Center = [NextChar, NextChar],
  13.     center_found (RestOfInput, RestOfStack, [NextChar, NextChar|RestOfStack],
  14.           Center, Largest);
  15.  
  16. no_center_found ([NextChar1, NextChar2|RestOfInput], [NextChar2|RestOfStack],
  17.          Largest) ->
  18.     Center = [NextChar2, NextChar1, NextChar2],
  19.     center_found (RestOfInput, RestOfStack,
  20.           [NextChar2, NextChar1, NextChar2|RestOfStack], Center,
  21.           Largest);
  22.  
  23. no_center_found ([NextChar|RestOfInput], Stack, Largest) ->
  24.     no_center_found (RestOfInput, [NextChar|Stack], Largest).
  25.    
  26.  
  27. center_found (_RemainingInput = [], _Stack = [], _, Center, Largest) ->
  28.     if length (Center) > length (Largest) -> Center;
  29.        true -> Largest
  30.     end;
  31.  
  32. center_found (_RemainingInput = [], [TopOfStack|RestOfStack], SavedStack, Center,
  33.           Largest) ->
  34.     Last = lists:last (Center),
  35.     case (Last == TopOfStack) and ([Last|Center] == lists:reverse ([Last|Center])) of
  36.         true ->
  37.         NewCenter = [Last|Center],
  38.         if length (NewCenter) > length (Largest) ->
  39.             center_found ([], RestOfStack, SavedStack, NewCenter,
  40.                   NewCenter);
  41.            true -> Largest
  42.         end;
  43.         _ ->
  44.         if length (Center) > length (Largest) -> Center;
  45.            true -> Largest
  46.         end
  47.     end;
  48.  
  49. center_found (RemainingInput, Stack = [], SavedStack, Center, Largest) ->
  50.     if length (Center) > length (Largest) ->
  51.         no_center_found (RemainingInput, SavedStack, Center);
  52.        true ->
  53.         no_center_found (RemainingInput, SavedStack, Largest)
  54.     end;
  55.  
  56. center_found ([NextChar|RestOfInput], [NextChar|RestOfStack], SavedStack, Center,
  57.           Largest) ->
  58.     center_found (RestOfInput, RestOfStack,
  59.           [NextChar|SavedStack],
  60.           lists:concat([NextChar|Center],[NextChar]),
  61.           Largest);
  62.  
  63. center_found ([NextChar|RestOfInput], [TopOfStack|RestOfStack], SavedStack, Center,
  64.           Largest) ->
  65.     Last = lists:last (Center),
  66.     case (NextChar == Last) and ([Last|Center] == lists:reverse ([Last|Center])) of
  67.         true ->
  68.         NewCenter = [Last|Center],
  69.         if length (NewCenter) > length (Largest) ->
  70.             center_found (RestOfInput, [TopOfStack|RestOfStack],
  71.                   [NextChar|SavedStack],
  72.                   NewCenter, NewCenter);
  73.            true ->
  74.             center_found (RestOfInput, [TopOfStack|RestOfStack],
  75.                   [NextChar|SavedStack],
  76.                   NewCenter, Largest)
  77.         end;
  78.         _ ->
  79.         if length (Center) > length (Largest) ->
  80.             no_center_found (RestOfInput, [NextChar|SavedStack], Center);
  81.            true ->
  82.             no_center_found (RestOfInput, [NextChar|SavedStack], Largest)
  83.         end
  84.     end.
  85.  
  86.  
  87. test() ->
  88.     io:format("~p ~n", [maximal_palindrome_in ("abcde")]),
  89.     io:format("~p ~n", [maximal_palindrome_in ("abbbaeeeeee")]),
  90.     io:format("~p ~n", [maximal_palindrome_in ("abcdcbaabcdc")]).
  91.  
  92.  
  93. 1> palindrome:test().
  94. []
  95. "eeeeee"
  96. "cdcbaabcdc"
  97. ok
Advertisement
Add Comment
Please, Sign In to add comment