Longest Common Contiguous Sublist (Dynamic Programming)

/* lcs_con(As, Bs, L, I, J) is true if L is the length of the longest common */
/*   contiguous sublist of the lists As and Bs, and this sublist ends at     */
/*   position I of As and position J of Bs.                                  */
/* e.g. lcs_con([4,5,2,2,3], [1,2,3,4,1], L, I, J). gives L=2 I=5 J=3        */
/*                     * *      * *                                          */
lcs_con(As, Bs, L, I, J):-
  length(Bs, Length),
  replicate(Length, 0, FirstRow),
  lcs_con_1(As, Bs, 1, [0|FirstRow], a(0,0,0), a(L,I,J)).

% e.g. lcs_con_1([4,5,2,2,3], [1,2,3,4,1], 1, [0,0,0,0,0,0], a(0,0,0), X).
%   gives X=a(2,5,3)
% Note: The J-th element in the row corresponding to the I-th element of As
%   is the maximum length of common sublists that end at position I of As and
%   position J of Bs
lcs_con_1([], _, _, _, Solution, Solution).
lcs_con_1([A|As], Bs, I, PreviousRow, Solution0, Solution):-
  lcs_con_2(Bs, A, I, 1, PreviousRow, NextRow, Solution0, Solution1),
  I1 is I + 1,
  lcs_con_1(As, Bs, I1, [0|NextRow], Solution1, Solution).

lcs_con_2([], _, _, _, _, [], Solution, Solution).
lcs_con_2([A|Bs], A, I, J, PreviousRow, [Item|NextRow], Solution0, Solution):-
  nth_member(PreviousRow, J, Item1), !,
  Item is Item1 + 1,
  lcs_con_3(Solution0, Item, I, J, Solution1),
  J1 is J + 1,
  lcs_con_2(Bs, A, I, J1, PreviousRow, NextRow, Solution1, Solution).
lcs_con_2([_|Bs], A, I, J, PreviousRow, [0|NextRow], Solution0, Solution):-
  J1 is J + 1,
  lcs_con_2(Bs, A, I, J1, PreviousRow, NextRow, Solution0, Solution).
  
lcs_con_3(a(Len,_,_), Item, I, J, a(Item,I,J)):-
  Item > Len, !.
lcs_con_3(Solution, _, _, _, Solution).

/* length(Xs, L) is true if L is the number of elements in the list Xs.      */
%length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of        */
/*   elements in the list Xs.                                                */
%length_1([], L, L).
%length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).

/* nth_member(+Xs, ?N, ?X) is true if X is the N-th (base 1) element of the  */
/*   list Xs.                                                                */
nth_member(Xs, N, X):-nth_member_1(Xs, X, 1, N).

nth_member_1([X|_], X, I, I).
nth_member_1([_|Xs], X, I0, I):-
  I1 is I0 + 1,
  nth_member_1(Xs, X, I1, I).
  
/* replicate(N, X, Xs) is true if the list Xs contains N occurrences of the  */
/*   item X.                                                                 */
replicate(0, _, []):-!.  
replicate(I, X, [X|Xs]):-
  I > 0,
  I1 is I - 1,
  replicate(I1, X, Xs).

test:-
  X=[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,
     8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4,5,9,2,3,0,7,8,1,6,
     4,0,6,2,8,6,2,0,8,9,9,8,6,2,8,0,3,4,8,2,5,3,4,2,1,1,7,0,6,7,9,8,2,1,4,
     8,0,8,6,5,1,3,2,8,2,3,0,6,6,4,7,0,9,3,8,4,4,6,0,9,5,5,0,5,8,2,2,3,1,7],
%                                * * * * *
  Y=[2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,6,0,2,8,7,4,7,1,3,5,2,6,6,2,4,
     9,7,7,5,7,2,4,7,0,9,3,6,9,9,9,5,9,5,7,4,9,6,6,9,6,7,6,2,7,7,2,4,0,7,6,
%                * * * * *
     6,3,0,3,5,3,5,4,7,5,9,4,5,7,1,3,8,2,1,7,8,5,2,5,1,6,6,4,2,7,4,2,7,4,6,
     6,3,9,1,9,3,2,0,0,3,0,5,9,9,2,1,8,1,7,4,1,3,5,9,6,6,2,9,0,4,3,5,7,2,9],
  lcs_con(X, Y, L, I, J),
  write([L,I,J]), nl. % L=5 I=124 J=46

LPA Index     Home Page