Border
Let u be a non-empty word. A border of u is a word different from u which is both prefix and suffix of u. For example, the word u = abacaba has the three borders ε, a and aba. Let us note BORDER( x ) the longest border of a non-empty word x.
This implementation of Erlang of BORDER(x) is a bit convoluted, infriges on Christian’s fatwah on mixing printing and computations and function overloading [can’t win them all in one day], but it seems to work. As a bonus it calculates the length, β, and the border itself all in one go.
-module(rinder).
-compile(export_all).
border(A) ->
AA=list_to_tuple(A),
SA=size(AA),
Len=trunc(SA/2),
Len2=Len * 2,
case SA of
Len2 -> Len3 = Len-1;
_ -> Len3 = Len
end,
io:format("Max length of border: ~p~n",[Len3]),
io:format("Min value of u: ~p~n",[lists:sublist(A,Len3+1,SA-Len3-Len3)]),
H=element(1,AA),
T=element(SA,AA),
case H of
T -> io:format(" => Border of size 1, ~p~n",[[T]]), border(AA,Len3,1,1,2);
_ -> io:format(" => No border size of 1~n",[]), border(AA,Len3,0,1,2)
end.border(A,Len3,Temp,Cnt,Current) when Current > Len3 ->
case Temp of
0 -> {0,[]};
N -> {N,lists:sublist(tuple_to_list(A),1,N)}
end;
border(A,Len3,Temp,Cnt,Current) when Cnt > Current ->
io:format(" => Border of size ~p, ~p~n",[Current,lists:sublist(tuple_to_list(A),1,Current)]),
border(A,Len3,Current,1,Current+1);
border(A,Len3,Temp,Cnt,Current) ->
Cond = element(Cnt,A),
Cond2 = element(size(A)-Current+Cnt,A),
case Cond of
Cond2 ->
border(A,Len3, Temp, Cnt+1, Current);
_ ->
io:format(" => No border of size ~p~n",[Current]),
border(A,Len3, Temp, 1, Current+1)
end.
1> rinder:border("abacXababa").
Max length of border: 4
Min value of u: "Xa"
=> Border of size 1, "a"
=> No border of size 2
=> Border of size 3, "aba"
=> No border of size 4
{3,"aba"}
2> rinder:border("ababbb").
Max length of border: 2
Min value of u: "ab"
=> No border size of 1
=> No border of size 2
{0,[]}
3> rinder:border("babbaa").
Max length of border: 2
Min value of u: "bb"
=> No border size of 1
=> No border of size 2
{0,[]}
4> rinder:border("abaaab").
Max length of border: 2
Min value of u: "aa"
=> No border size of 1
=> Border of size 2, "ab"
{2,"ab"}
5> rinder:border("abbaab").
Max length of border: 2
Min value of u: "ba"
=> No border size of 1
=> Border of size 2, "ab"
{2,"ab"}
I’ve played with a few more examples – examples 2 to 5 are from Christian’s coursework – and it seems to work.
The API entry takes a string/list as argument, converts it to a tuple, and computes the maximum hypothetical length of the border: since the word surrounded by the border can’t be null, you need to leave at least 1 character. So, if |x| is even, you need to take (|x|/2)-1, otherwise int(|x|/2). And since Erlang seems to miss a modulo function, I have to go through the Len=int(|x|), Len2=Len*2 hoop. Grrr…
The code tests the first possible border, of size one, by comparing the first and last element of the tuple. If they match the Temp variable [which records the highest length so far] is set to 1, otherwise to 0, while calling border/4. Then the code basically goes from 2 to Len3, recorded in Current, calling border/5, which itself goes from 1 to Current, testing the Cnt first/last elements of the tuple. Crude but works. When all is done, the largest border and its length are returned.