Algol 68 Genie

longest-common-sequence.a68

     
   1  COMMENT
   2  
   3  @section Synopsis
   4  
   5  Compute longest common subsequence of strings.
   6  
   7  A subsequence is any output string obtained by deleting zero or more symbols from an input string.
   8  The longest common subsequence (LCS) is a subsequence of maximum length common to two (or more) strings.
   9  
  10  After the program published on Rosetta Code by Marcel van der Veer.
  11  
  12  This is a brute force recursive solution.
  13  If the strings have respective lengths L_s and L_t, the time complexity is O(2^(L_s + L_t)).
  14  
  15  COMMENT
  16  
  17  BEGIN PROC lcs = (STRING s, t) STRING:
  18        IF LWB s > UPB s OR LWB t > UPB t
  19        THEN # Trivial case: empty strings have an empty LCS. #
  20             ""
  21        ELIF s[UPB s] = t[UPB t]
  22        THEN # If the last characters of 's' and 't' match, prepend the LCS of the preceeding strings #
  23             lcs (s[: UPB s - 1], t[: UPB t - 1]) + s[UPB s]
  24        ELSE # Find the longest LCS of these cases:
  25               (1) excluding the last character of 's' including the last of 't',
  26               (2) excluding the last character of 't' including the last of 's'. #
  27             STRING u = lcs (s[: UPB s - 1], t), v = lcs (s, t[: UPB t - 1]);
  28             (UPB u > UPB v | u | v)
  29        FI;
  30  
  31        print ((lcs ("1234", "1224533324"), new line));
  32        print((lcs ("thisisatest", "testing123testing"), new line))
  33  END

Deze website is gearchiveerd door de KB, nationale bibliotheek.

This website is archived by the National Library of the Netherlands.