跳转到内容

算法实现/字符串/最长公共子序列

来自维基教科书,开放的书籍,为开放的世界

查找 LCS

[编辑 | 编辑源代码]

以下 C# 程序计算两个字符串的最长公共子序列(注意是单数)。例如,对于字符串 "computer" 和 "houseboat",此算法返回一个值为 3 的结果,具体来说是字符串 "out"。

计算 LCS 的长度表

[编辑 | 编辑源代码]
        static int[,] LCS(string s1, string s2)
        {
            int[,] c = new int[s1.Length + 1, s2.Length + 1];
            for (int i = 1; i <= s1.Length; i++)
                for (int j = 1; j <= s2.Length; j++)
                {
                    if (s1[i - 1] == s2[j - 1])
                        c[i, j] = c[i - 1, j - 1] + 1;
                    else                   
                        c[i, j] = c[i - 1, j] > c[i, j - 1]? c[i - 1, j] : c[i, j - 1];
                }
            return c;
        }

读出 LCS

[编辑 | 编辑源代码]
        static string BackTrack(int[,] c, string s1, string s2, int i, int j)
        {
            if (i == 0 || j == 0) 
                return "";
            else if (s1[i - 1] == s2[j - 1])
                return BackTrack(c, s1, s2, i - 1, j - 1) + s1[i - 1];
            else if (c[i, j - 1] > c[i - 1, j])
                return BackTrack(c, s1, s2, i, j - 1);
            else
                return BackTrack(c, s1, s2, i - 1, j);
        }
[编辑 | 编辑源代码]
        static string PrintDiff(int[,] c, string s1, string s2, int i, int j)
        {
            var a = "";
           
            if (i > 0 && j > 0 && s1[i - 1] == s2[j - 1])
            {
                a = PrintDiff(c, s1, s2, i - 1, j - 1);
                return a + "" + s1[i - 1];
            }
            else if (j > 0 && (i == 0 || (c[i, j - 1] > c[i - 1, j])))
            {
                a = PrintDiff(c, s1, s2, i, j - 1);
                return a + "+" + s2[j - 1];
            }
            else if (i > 0 && (j == 0 || (c[i, j - 1] <= c[i - 1, j])))
            {
                a = PrintDiff(c, s1, s2, i - 1, j);
                return a + "-" + s1[i - 1];
            }
            return a;
        }

示例用法

[编辑 | 编辑源代码]
        static void Main(string[] args)
        {
            string s1 = "computer";
            string s2 = "houseboat";

            var c = LCS(s1, s2);
            Console.WriteLine(BackTrack(c, s1, s2, s1.Length, s2.Length)); //out
            Console.WriteLine(PrintDiff(c, s1, s2, s1.Length, s2.Length)); //+h-co-m-pu+s+e+b+o+at-e-r

            Console.ReadLine();
        }


Common Lisp

[编辑 | 编辑源代码]

此版本仅适用于列表,但可以推广到所有序列。

(defun lcs-list (list-1 list-2 &key (test #'eql))
  "Find the longest common subsequence of LIST-1 and LIST-2 using TEST."
  (cond
    ((null list-1) nil)
    ((null list-2) nil)
    ((funcall test (first list-1) (first list-2))
       (cons (first list-1) (lcs-list (rest list-1) (rest list-2) :test test)))
    (t (let ((lcs-1 (lcs-list list-1 (rest list-2) :test test))
             (lcs-2 (lcs-list (rest list-1) list-2 :test test)))
         (if (> (length lcs-1) (length lcs-2))
           lcs-1

           lcs-2)))))

(defun diff (list1 list2 &key (test #'eql))
  "Find the differences between LIST1 and LIST2 using TEST."
  (let ((lcs (lcs-list list1 list2 :test test))
        result)
    (dolist (c lcs)
      (let* ((sync-list1 (position c list1 :test test))
             (sync-list2 (position c list2 :test test))
             (removed (subseq list1 0 sync-list1))
             (added (subseq list2 0 sync-list2)))
        (setf list1 (subseq list1 (1+ sync-list1)))
        (setf list2 (subseq list2 (1+ sync-list2)))
        (when removed
          (push (cons :removed removed) result))
        (when added
          (push (cons :added added) result))
        (push c result)))
    (when list1
      (push (cons :removed list1) result))
    (when list2
      (push (cons :added list2) result))
    (nreverse result)))

计算 LCS 的长度表

[编辑 | 编辑源代码]
def LCS(X, Y):
    m = len(X)
    n = len(Y)
    # An (m+1) times (n+1) matrix
    C = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]: 
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j-1], C[i-1][j])
    return C

读出 LCS

[编辑 | 编辑源代码]
def backTrack(C, X, Y, i, j):
    if i == 0 or j == 0:
        return ""
    elif X[i-1] == Y[j-1]:
        return backTrack(C, X, Y, i-1, j-1) + X[i-1]
    else:
        if C[i][j-1] > C[i-1][j]:
            return backTrack(C, X, Y, i, j-1)
        else:
            return backTrack(C, X, Y, i-1, j)

读出所有 LCS

[编辑 | 编辑源代码]
def backTrackAll(C, X, Y, i, j):
    if i == 0 or j == 0:
        return set([""])
    elif X[i-1] == Y[j-1]:
        return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1, j-1)])
    else:
        R = set()
        if C[i][j-1] >= C[i-1][j]:
            R.update(backTrackAll(C, X, Y, i, j-1))
        if C[i-1][j] >= C[i][j-1]:
            R.update(backTrackAll(C, X, Y, i-1, j))
        return R

用法示例

[编辑 | 编辑源代码]
X = "AATCC"
Y = "ACACG"
m = len(X)
n = len(Y)
C = LCS(X, Y)
 
print "Some LCS: '%s'" % backTrack(C, X, Y, m, n)
print "All LCSs: %s" % backTrackAll(C, X, Y, m, n)

它打印以下内容

Some LCS: 'AAC'
All LCSs: set(['ACC', 'AAC'])
[编辑 | 编辑源代码]
def printDiff(C, X, Y, i, j):
    if i > 0 and j > 0 and X[i-1] == Y[j-1]:
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i-1]
    else:
        if j > 0 and (i == 0 or C[i][j-1] >= C[i-1][j]):
            printDiff(C, X, Y, i, j-1)
            print "+ " + Y[j-1]
        elif i > 0 and (j == 0 or C[i][j-1] < C[i-1][j]):
            printDiff(C, X, Y, i-1, j)
            print "- " + X[i-1]

用法示例

[编辑 | 编辑源代码]
X = [
    "This part of the document has stayed",
    "the same from version to version.",
    "",
    "This paragraph contains text that is",
    "outdated - it will be deprecated '''and'''",
    "deleted '''in''' the near future.",
    "",
    "It is important to spell check this",
    "dokument. On the other hand, a misspelled",
    "word isn't the end of the world.",
]
Y = [
    "This is an important notice! It should",
    "therefore be located at the beginning of",
    "this document!",
    "",
    "This part of the document has stayed",
    "the same from version to version.",
    "",
    "It is important to spell check this",
    "document. On the other hand, a misspelled",
    "word isn't the end of the world. This",
    "paragraph contains important new",
    "additions to this document.",
]

C = LCS(X, Y)
printDiff(C, X, Y, len(X), len(Y))

它打印以下内容

+ This is an important notice! It should
+ therefore be located at the beginning of
+ this document!
+ 
  This part of the document has stayed
  the same from version to version.
- 
- This paragraph contains text that is
- outdated - it will be deprecated and
- deleted in the near future.
  
  It is important to spell check this
- dokument. On the other hand, a misspelled
- word isn't the end of the world.
+ document. On the other hand, a misspelled
+ word isn't the end of the world. This
+ paragraph contains important new
+ additions to this document.

以下 VB.NET 程序计算两个字符串的最长公共子序列(注意是单数)。例如,对于字符串 "computer" 和 "houseboat",此算法返回一个值为 3 的结果,具体来说是字符串 "out"。

Public Function LongestCommonSubsequence(ByVal s1 As String, ByVal s2 As String) As Integer

	'Bulletproofing - 1 or both inputs contains nothing
	If s1.Length.Equals(0) Or s2.Length.Equals(0) Then
        	Return "0"
        End If

        '*** Actual Algorithm From Here ***
        Dim num(s1.Length - 1, s2.Length - 1) As Long       '2D Array
        Dim letter1 As Char = Nothing
        Dim letter2 As Char = Nothing
        For i As Integer = 0 To s1.Length - 1

        	For j As Integer = 0 To s2.Length - 1

                	letter1 = s1.Chars(i)
                	letter2 = s2.Chars(j)

                	If letter1.Equals(letter2) Then
                    	        If i.Equals(0) Or j.Equals(0) Then  'The first elements respectively
                        	        num(i, j) = 1
                    	        Else
                        	        num(i, j) = 1 + num(i - 1, j - 1)
                    	        End If
                	Else
                    		If i.Equals(0) And j.Equals(0) Then
                        		num(i, j) = 0
                    		ElseIf i.Equals(0) And Not j.Equals(0) Then    'First ith element
                        		num(i, j) = Math.Max(0, num(i, j - 1))
                    		ElseIf j.Equals(0) And Not i.Equals(0) Then   'First jth element
                        		num(i, j) = Math.Max(num(i - 1, j), 0)
                    		ElseIf i <> 0 And j <> 0 Then
                        		num(i, j) = Math.Max(num(i - 1, j), num(i, j - 1))
                    		End If
                	End If
            	Next j
        Next i

        Return num(s1.Length - 1, s2.Length - 1)

End Function

Usage: LongestCommonSubsequence("computer", "houseboat")
public static <E> List<E> LongestCommonSubsequence(E[] s1, E[] s2)
{
        int[][] num = new int[s1.length+1][s2.length+1];  //2D array, initialized to 0

        //Actual algorithm
        for (int i = 1; i <= s1.length; i++)
                for (int j = 1; j <= s2.length; j++)
                        if (s1[i-1].equals(s2[j-1]))
                                num[i][j] = 1 + num[i-1][j-1];
                        else
                                num[i][j] = Math.max(num[i-1][j], num[i][j-1]);

        System.out.println("length of LCS = " + num[s1.length][s2.length]);

        int s1position = s1.length, s2position = s2.length;
        List<E> result = new LinkedList<E>();

        while (s1position != 0 && s2position != 0)
        {
                if (s1[s1position - 1].equals(s2[s2position - 1]))
                {
                        result.add(s1[s1position - 1]);
                        s1position--;
                        s2position--;
                }
                else if (num[s1position][s2position - 1] >= num[s1position][s2position])
                {
                        s2position--;
                }
                else
                {
                        s1position--;
                }
        }
        Collections.reverse(result);
        return result;
}

Java 实现使用两个类。第一个是实现该算法的抽象类。第二个是为字符串实现此功能的具体类。显然,您可以使用此类,以便它不是比较字符串中的字符,而是比较文件中的行、代码块、XML 文档中的节点,或您选择的任何内容。

import static java.lang.Math.*;

import java.util.ArrayList;
import java.util.List;
import static java.lang.Math.*;
/**
 * A class to compute the longest common subsequence in two strings.  
 * Algorithms from Wikipedia:
 * http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
 * 
 * @author jhess
 *
 */
public abstract class LongestCommonSubsequence<VALUE> {
	private int[][] c;
	private ArrayList<DiffEntry<VALUE>> diff;
	private ArrayList<VALUE> backtrack;
	

	/**
	 * A constructor for classes inheriting this one, allowing them to 
	 * do some initialization before setting the values of X and Y.  Once 
	 * the initialization is complete, the inheriting class must call
	 * initValues(VALUE[] x, VALUE[] y)
	 */
	protected LongestCommonSubsequence() {
		
	}
	
	protected abstract int lengthOfY() ;
	protected abstract int lengthOfX() ;
	protected abstract VALUE valueOfX(int index) ;
	protected abstract VALUE valueOfY(int index) ;
	
	protected boolean equals(VALUE x1, VALUE y1) {
		return (null == x1 && null == y1) || x1.equals(y1);
	}

	
	private boolean isXYEqual(int i, int j) {
		return equals(valueOfXInternal(i),valueOfYInternal(j));
	}
	
	private VALUE valueOfXInternal(int i) {
		return valueOfX(i-1);
	}
	
	private VALUE valueOfYInternal(int j) {
		return valueOfY(j-1);
	}
	
	public void calculateLcs() {
		if(c != null) {
			return;
		}
		c = new int[lengthOfX()+1][];
		for(int i = 0; i < c.length; i++) {
			c[i] = new int[lengthOfY()+1];
		}

		for(int i = 1; i < c.length; i++) {
			for(int j = 1; j < c[i].length; j++) {
				if(isXYEqual(i, j)) {
					c[i][j] = c[i-1][j-1] + 1;
				} else {
					c[i][j] = max(c[i][j-1], c[i-1][j]);
				}
			}
		}
	}

	public int getLcsLength() {
		calculateLcs();

		return c[lengthOfX()][lengthOfY()];
	}
	
	public int getMinEditDistance() {
		calculateLcs();
		return lengthOfX()+lengthOfY()-2*abs(getLcsLength());
	}
	
	public List<VALUE> backtrack() {
		calculateLcs();
		if(this.backtrack == null) {
			this.backtrack = new ArrayList<VALUE>();
			backtrack(lengthOfX(),lengthOfY());
		}
		return this.backtrack;
	}
	
	public void backtrack(int i, int j) {
		calculateLcs();
		
		if (i == 0 || j == 0) {
			return;
		}
		else if (isXYEqual(i, j)) {
			backtrack(i-1,j-1);
			backtrack.add(valueOfXInternal(i));
		} 
		else {
			if(c[i][j-1] > c[i-1][j]) {
				backtrack(i,j-1);
			} else {
				backtrack(i-1,j);
			}
		}
	}
	
	public List<DiffEntry<VALUE>> diff() {
		calculateLcs();
		
		if(this.diff == null) {
			this.diff = new ArrayList<DiffEntry<VALUE>>();
			diff(lengthOfX(),lengthOfY()); 
		}
		return this.diff;
	}
	
	private void diff(int i, int j) {
		calculateLcs();

		while(!(i==0 && j==0)) {
			if (i > 0 && j > 0 && isXYEqual(i, j)) {
				this.diff.add(new DiffEntry<VALUE>(DiffType.NONE,
						valueOfXInternal(i)));
				i--;j--;
				
			} else {
				if (j > 0 && (i == 0 || c[i][j - 1] >= c[i - 1][j])) {
					this.diff.add(new DiffEntry<VALUE>(DiffType.ADD,
							valueOfYInternal(j)));
					j--;
					
				} else if (i > 0 && (j == 0 || c[i][j - 1] < c[i - 1][j])) {
					
					this.diff.add(new DiffEntry<VALUE>(DiffType.REMOVE,
							valueOfXInternal(i)));
					i--;
				}
			}
		}
		
		Collections.reverse(this.diff);
	}
	
	@Override
	public String toString() {
		calculateLcs();

		StringBuffer buf = new StringBuffer();
		buf.append("  ");
		for(int j = 1; j <= lengthOfY(); j++) {
			buf.append(valueOfYInternal(j));
		}
		buf.append("\n");
		buf.append(" ");
		for(int j = 0; j < c[0].length; j++) {
			buf.append(Integer.toString(c[0][j]));
		}
		buf.append("\n");
		for(int i = 1; i < c.length; i++) {
			buf.append(valueOfXInternal(i));
			for(int j = 0; j < c[i].length; j++) {
				buf.append(Integer.toString(c[i][j]));
			}
			buf.append("\n");
		}
		return buf.toString();
	}
	
	public static enum DiffType {
		ADD("+","add"),REMOVE("-","remove"),NONE(" ","none");
		
		private String val;
		private String name;
		
		DiffType(String val, String name) {
			this.val = val;
			this.name = name;
		}
		
		@Override
		public String toString() {
			return val;
		}

		public String getName() {
			return name;
		}

		public String getVal() {
			return val;
		}
	}
	
	public static class DiffEntry<VALUE> {
		private DiffType type;
		private VALUE value;
		
		public DiffEntry(DiffType type, VALUE value) {
			super();
			this.type = type;
			this.value = value;
		}
		
		public DiffType getType() {
			return type;
		}
		public void setType(DiffType type) {
			this.type = type;
		}
		public VALUE getValue() {
			return value;
		}
		public void setValue(VALUE value) {
			this.value = value;
		}
		
		@Override
		public String toString() {
			return type.toString()+value.toString();
		}
		
	}
	
	
}
import java.util.List;

public class LcsString extends LongestCommonSubsequence<Character> {
	private String x;
	private String y;
	
	public LcsString(String from, String to) {
		this.x = from;
		this.y = to;
	}
	
	protected int lengthOfY() {
		return y.length();
	}
	protected int lengthOfX() {
		return x.length();
	}
	protected Character valueOfX(int index) {
		return x.charAt(index);
	}
	protected Character valueOfY(int index) {
		return y.charAt(index);
	}

	public String getHtmlDiff() {
		DiffType type = null;
		List<DiffEntry<Character>> diffs = diff();
		StringBuffer buf = new StringBuffer();
		
		for(DiffEntry<Character> entry : diffs) {
			if(type != entry.getType()) {
				if(type != null) {
					buf.append("</span>");
				}
				buf.append("<span class=\""+entry.getType().getName()+"\">");
				type = entry.getType();
			}
			buf.append(escapeHtml(entry.getValue()));
		}
		buf.append("</span>");
		return buf.toString();
	}
	
	private String escapeHtml(Character ch) {
		switch(ch) {
		case '<' : return "&lt;";
		case '>' : return "&gt;";
		case '"' : return "\\&quot;";
		default : return ch.toString();
		}
	}

// EXAMPLE.  Here's how you use it.  
	public static void main(String[] args) {
		LcsString seq = new LcsString("<p>the quick brown fox</p>","<p>the <b>Fast</b> brown dog</p>");
		System.out.println("LCS: "+seq.getLcsLength());
		System.out.println("Edit Dist: "+seq.getMinEditDistance());
		System.out.println("Backtrack: "+seq.backtrack());
		System.out.println("HTML Diff: "+seq.getHtmlDiff());
	}
	
}
#include <algorithm>
#include <string>
#include <vector>

#include <stdio.h>
#include <string.h>

// See http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node4.html.
class LCS
{
    class LCSTable
    {
        size_t   m_;
        size_t   n_;
        size_t*  data_;
    public:
        LCSTable(size_t m, size_t n)
        : m_(m)
        , n_(n)
        {
            data_ = new size_t[(m_ + 1) * (n_ + 1)];
        }
        ~LCSTable()
        {
            delete [] data_;
        }

        void setAt(size_t i, size_t j, size_t value)
        {
            data_[i + j * (m_ + 1)] = value;
        }

        size_t getAt(size_t i, size_t j) const
        {
            return data_[i + j * (m_ + 1)];
        }

        template<typename T> void
        build(const T* X, const T* Y)
        {
            for (size_t i=0; i<=m_; ++i)
                setAt(i, 0, 0);

            for (size_t j=0; j<=n_; ++j)
                setAt(0, j, 0);

            for (size_t i = 0; i < m_; ++i)
            {
                for (size_t j = 0; j < n_; ++j)
                {
                    if (X[i] == Y[j])
                        setAt(i+1, j+1, getAt(i, j)+1);
                    else
                        setAt(i+1, j+1, std::max(getAt(i+1, j), getAt(i, j+1)));
                }
            }
        }
    };

    template<typename T> static void
    backtrackOne(const LCSTable& table,
                 const T* X, const T* Y, size_t i, size_t j,
                 std::vector<T>& result)
    {
        result.clear();
        if (i == 0 || j == 0)
            return;
        if (X[i - 1] == Y[j - 1])
        {
            backtrackOne(table, X, Y, i - 1, j - 1, result);
            result.push_back(X[i - 1]);
            return;
        }
        if (table.getAt(i, j - 1) > table.getAt(i -1, j))
            backtrackOne(table, X, Y, i, j - 1, result);
        else
            backtrackOne(table, X, Y, i - 1, j, result);
    }

public:
    template<typename T> static void
    findOne(T* X, size_t m, T* Y, size_t n,
            std::vector<T>& result)
    {
        LCSTable table(m, n);
        table.build(X, Y);
        backtrackOne(table, X, Y, m, n, result);
    }
};

用法

    char X[] = "XMJYAUZ";
    char Y[] = "MZJAWXU";
    std::vector<char> result;

    LCS::findOne(X, strlen(X), Y, strlen(Y), result);
    std::string resultString(&result.front(), result.size());
def subsequence(s1, s2)

        return 0 if s1.empty? || s2.empty?

        num=Array.new(s1.size){Array.new(s2.size)}
        s1.scan(/./).each_with_index{|letter1,i|
            s2.scan(/./).each_with_index{|letter2,j|

                    if s1[i]==s2[j]
                        if i==0||j==0
                           num[i][j] = 1
                        else
                           num[i][j]  = 1 + num[i - 1][ j - 1]
                        end
                    else
                        if i==0 && j==0
                           num[i][j] = 0
                        elsif i==0 &&  j!=0  #First ith element
                           num[i][j] = [0,  num[i][j - 1]].max
                        elsif j==0 && i!=0  #First jth element
                            num[i][j] = [0, num[i - 1][j]].max
                        elsif i != 0 && j!= 0
                          num[i][j] = [num[i - 1][j], num[i][j - 1]].max
                        end
                    end
            }
        }
        num[s1.length - 1][s2.length - 1]

end

puts subsequence("houseboat","computer")

JavaScript

[编辑 | 编辑源代码]
function LCS(a, b) {
    var m = a.length, n = b.length,
        C = [], i, j;
    for (i = 0; i <= m; i++) C.push([0]);
    for (j = 0; j < n; j++) C[0].push(0);
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            C[i+1][j+1] = a[i] === b[j] ? C[i][j]+1 : Math.max(C[i+1][j], C[i][j+1]);
    return (function bt(i, j) {
        if (i*j === 0) { return ""; }
        if (a[i-1] === b[j-1]) { return bt(i-1, j-1) + a[i-1]; }
        return (C[i][j-1] > C[i-1][j]) ? bt(i, j-1) : bt(i-1, j);
    }(m, n));
}
function lcs(sequence a, b)
sequence res = ""
    if length(a) and length(b) then
        if a[$]=b[$] then
            res = lcs(a[1..-2],b[1..-2])&a[$]
        else
            sequence l = lcs(a,b[1..-2]),
                     r = lcs(a[1..-2],b)
            res = iff(length(l)>length(r)?l:r)
        end if
    end if
    return res
end function
<?php
/**
 * Class LCS - Using this class to calculate the LCS(Longest common subsequence)
 * You can pass both the strings in String format in the constructor when you are initializing the class
 * All the subsequent method calls are in the constructor and you can access the results using the $remains and $differences
 * public variables
 */
class LCS{
    
    // Define the class variables
    public $remains;
    public $differences;

    public function __construct($str1, $str2)
    {

        // The algorithm requires us to have m+1 by n+1 matrix starting with leading 0
        // for the initial matrix. Here we convert string to array and add the 0 as the first element
        $this->remains = "";
        $this->differences = "";

        $arr1 = array_merge([0], str_split($str1));
        $arr2 = array_merge([0], str_split($str2));

        $matrix = $this->generateMatrix($arr1, $arr2);
        $this->calculateDifference($matrix, $arr1, $arr2, count($arr1)-1, count($arr2)-1);

        return;
    }

    /**
     * @function calculateDifference - To use recursively and build the ending result of 
     * the backtrace using the LCS matrix
     * 
     * @input $matrix - 2D array of the values generated with the generateMatrix function
     * @input $first - Array of the characters for the first string with required leading 0th element
     * @input $second - Array of the characters for the second(result) string with required leading 0th element
     * @input $i - Position of the current element for the $first array
     * @input $j - Position of the current element for the $second array
     * 
     * @return null - Building the data into a public class object that we access later
     */
    private function calculateDifference($matrix, $first, $second, $i, $j){
        if($i>0 && $j>0 && ($first[$i] == $second[$j])){
            
            // Match found go diagonally
            $this->calculateDifference($matrix, $first, $second, $i-1, $j-1);
            $this->remains .= $first[$i];
            $this->differences .= $first[$i];
            
        } else if($j > 0 && ($i == 0 || ($matrix[$i][$j-1] >= $matrix[$i-1][$j]))){
            // column end reached or row above value greater than the value in the left column
            $this->calculateDifference($matrix, $first, $second, $i, $j-1);
            $this->differences .= "+".$second[$j];
            
        } else if($i > 0 && ($j == 0 || $matrix[$i][$j-1] < $matrix[$i-1][$j])){
            // column end reached or row above value lesser than the value in the left column
            $this->calculateDifference($matrix, $first, $second, $i-1, $j);
            $this->differences .= "-".$first[$i];
            
        } else{
            // both zeroes reached the end
            return;
        }
    }
    /**
     * @function generateMatrix - Creates a traceback matrix for the LCS
     *  
     * @input $first - Array of the characters for the first string with required leading 0th element
     * @input $second - Array of the characters for the second(result) string with required leading 0th element
     * 
     * @return $matrix - 2D array of numeric values for tree matching
     */
    private function generateMatrix($first, $second)
    {
        // Set the 0th row and column to have numeric value of 0
        for($i=0; $i<=count($first); ++$i){
            $matrix[$i][0] = 0;
        }
        for($j=0; $j<=count($second); ++$j){
            $matrix[0][$j] = 0;  
        }
        // Populate the matrix
        for($i=1; $i<count($first); ++$i){
            for($j=1; $j<count($second); ++$j){
                // if current i-th and j-th element match increment the value in the matrix from the previous
                if($first[$i] == $second[$j])
                    $matrix[$i][$j] = $matrix[$i-1][$j-1]+1;
                // get the better adjacent calculated value so far from the matrix and use that value
                else
                    $matrix[$i][$j] = max($matrix[$i][$j-1], $matrix[$i-1][$j]);
            }
        }
        return($matrix);
    }

}

用法示例

[编辑 | 编辑源代码]

包含您的类文件,并通过将两个字符串传递给构造函数来实例化类的新的对象。通过使用 $obj->remains 和 $obj->differences 访问结果。

$obj= new LCS($str1, $str2);
echo $obj->remains;
echo $obj->differences;

计算 LCS 的长度

[编辑 | 编辑源代码]
 CLCSLength rarg;X;Y;i;j;shape;lastalike;words;B;jb
 //⍝ Computes the length of the Longest common sequence
 X Yrarg

 //⍝ Optimize by working with numbers instead of strings
 wordsXY
 XwordsX
 YwordsY

 //⍝ Optimize and reduce sets by removing similar trailing objects.
 shape-(X)(Y)
 lastalike-+/\(shapeX)=(shapeY)
 XlastalikeX
 YlastalikeY

 //⍝ C is a numeric matrix where the height is the shape of X
 //⍝ and the width is the shape of Y
 C(1+⊃,/¨X Y)0

 //⍝ Fill C with LCSlengths
 j1+⍳⍴Y
 jbj-1
 :For i :In 1+⍳⍴X
     BX[i-1]=Y
     C[i;B/j]1+C[i-1;B/jb]
     C[i;(~B)/j]\(~B)/C[i;jb]C[i-1;j]
 :EndFor

读出所有 LCS

[编辑 | 编辑源代码]
 RMakeDiff rarg;do;⎕IO;C;X;Y;i;j;t1;t2
 //⍝ Get the diff between two vectors given the LCS in rarg1
 //⍝ \ret [;1] 1=Added item, 0=Deleted item
 //⍝      [;2] index in rarg2
 //⍝      [;3] index in rarg3
 //⍝      [;4] The item 
 ⎕IO0
 C X Yrarg

 //⍝ Number of elements in each vector. This is the starting
 //⍝ point for the calculation below
 i j⊃,/¨,¨X Y

 //⍝ Add an empty item before each item... Needed
 X Y' ',¨X Y

 //⍝ Test 1
 t1{C i j  j>0:{i=0:1  C[i;j-1]C[i-1;j]:1  0}0  0}

 //⍝ Test 2
 t2{C i j  i>0:{j=0:1  C[i;j-1]<C[i-1;j]:1  0}0  0}

 //⍝ Walk the path and trace additions or removals of items recursivly
 do{
     C X Y i j sofar
     (i>0)(j>0)(X[i]Y[j]):∇ C X Y(i-1)(j-1)sofar
     t1 C i j:∇ C X Y(i)(j-1)(sofar1 i j(jY))
     t2 C i j:∇ C X Y(i-1)(j)(sofar0 i j(iX))
     sofar
 }

 //⍝ Shoot
 Rdo C X Y i j(0 40)

用法示例

[编辑 | 编辑源代码]
new'MZJAWXU'
old'XMJYAUZ'
CLCSLength old new
DMakeDiff C old new
DD

变量 D 是

0 1 0 X
1 2 2 Z
0 4 3 Y
1 5 5 W
1 5 6 X
0 7 7 Z
   lcs=: [: >./@, [: (* * 1 + >./\@:(_1&|.)@:|:^:2)^:_ [: ,&0@:,.&0 =/
   'XMJYAUZ' lcs 'MZJAWXU'
4

详情请参阅 [1]

import scalaz.Memo

def longestCommonSubsequence(s1: String, s2: String): String = {
  def longest(a: String, b: String) = if (a.length > b.length) a else b
  lazy val lcs: ((Int, Int)) => String = Memo.mutableHashMapMemo[(Int, Int), String] {
    case (0, _) => ""
    case (_, 0) => ""
    case (i, j) if s1(i - 1) == s2(j - 1) => lcs((i - 1, j - 1)) + s1(i - 1)
    case (i, j) => longest(lcs((i, j - 1)), lcs((i - 1, j)))
  }
  lcs((s1.length, s2.length))
}


华夏公益教科书