LCS是 Longest Common Subsequence 的缩写, 即最长公共子序列. 比如
A = a1a2.........an
B = b1b2.........bm
如果有 ai1ai2...aik = bj1bj2....bjk 并且 i1<i2<...<ik AND j1<j2<..<jk
那么 ai1ai2...aik  就是 A,B的一个公共子序列.  相应的最长公共子序列就是k最大的时候了.

LCS可以用来计算两个文本的相似程度,以及生物学上的基因比较等实际应用。 在我的程序中它用来找出两个文本中不同的块. 比如, 我有一个英文听写, 然后还有一个原文. 我想知道我的听写都是哪些地方出错了, 就要同原文就行比较.  LCS就可做到这些.

源码中的函数 LCS(String[] txt1, String[] txt2).  其中txt1,txt2分别是英文听写和原文, 用数组表示, 每个数组元素就是一个单词.  返回结果是一个MatchPair的数组, MatchPair用来存放匹配的位置. 比如最大公共子序列是 ai1ai2...aik = bj1bj2....bjk , 那么返回结果就是(i1,j1) (i2,j2) ...  (ik,jk).

其他两个函数 LCS_ND LCS_ND_refined 实现了同样的功能. 并且效率也挺高不少. 如果程序需要,建议用LCS_ND_refined

呵呵, 下面贴代码( 因为版式问题,代码很乱,可以考到eclipse或其他编辑器里再看)

public final class TextUtil {

 public static class MatchPair {
  public int x;

  public int y;

  MatchPair(int x, int y) {
   this.x = x;
   this.y = y;
  }
 }

 public static MatchPair[] LCS(String[] txt1, String[] txt2) {

  int[][] matchCount = null;
  int[][] direction = null;

  matchCount = new int[txt1.length + 1][txt2.length + 1];
  direction = new int[txt1.length + 1][txt2.length + 1];

  for (int i = 0; i <= txt1.length; ++i) {
   matchCount[i][0] = 0;
   direction[i][0] = 0;
  }

  for (int i = 0; i <= txt2.length; ++i) {
   matchCount[0][i] = 0;
   direction[0][i] = 0;
  }

  for (int plus = 2; plus <= txt1.length + txt2.length; ++plus) {
   for (int x = Math.max(1, plus - txt2.length); x <= Math.min(
     plus - 1, txt1.length); ++x) {
    int y = plus - x;
    int count = 0;
    int dir = 0;
    if (txt1[x - 1].equals(txt2[y - 1])) {
     count = matchCount[x - 1][y - 1] + 1;
     dir = 2;
    } else if (matchCount[x - 1][y] > matchCount[x][y - 1]) {
     count = matchCount[x - 1][y];
     dir = 1;
    } else {
     count = matchCount[x][y - 1];
     dir = 3;
    }

    matchCount[x][y] = count;
    direction[x][y] = dir;
   }
  }

  int x = txt1.length, y = txt2.length;
  ArrayList ret = new ArrayList();
  int dir = direction[x][y];
  while (dir != 0) {

   if (dir == 2) {
    ret.add(new MatchPair(x - 1, y - 1));
    --x;
    --y;
   } else if (dir == 1) {
    --x;
   } else {
    --y;
   }

   dir = direction[x][y];
  }

  Collections.reverse(ret);
  return (MatchPair[]) ret.toArray(new MatchPair[0]);
 }

 public static MatchPair[] LCS_DN(String[] txt1, String[] txt2) {
  ArrayList list = new ArrayList();

  int M = txt1.length;
  int N = txt2.length;
  int MAX = M + N;

  int[] cur = null;
  int[] pre = new int[2 * MAX + 1];

  pre[1 + MAX] = 0;

  int x, y;
  for (int D = 0; D <= MAX; ++D) {
   list.add(pre);
   cur = new int[2 * MAX + 1];

   for (int k = -1 * D; k <= D; k += 2) {
    if (k == -1 * D || k != D
      && pre[k - 1 + MAX] < pre[k + 1 + MAX]) {
     x = pre[k + 1 + MAX];
    } else {
     x = pre[k - 1 + MAX] + 1;
    }
    y = x - k;
    while (x < txt1.length && y < txt2.length
      && txt1[x].equals(txt2[y])) {
     ++x;
     ++y;
    }
    cur[k + MAX] = x;

    if (x == txt1.length && y == txt2.length) {
     int x1, k1;
     ArrayList ret = new ArrayList();
     do {
      pre = (int[]) list.get(D);
      if (k == -1 * D || k != D
        && pre[k - 1 + MAX] < pre[k + 1 + MAX]) {
       x1 = pre[k + 1 + MAX];
       k1 = k + 1;
      } else {
       x1 = pre[k - 1 + MAX];
       k1 = k - 1;
      }

      while (x > x1 && (x - k) > (x1 - k1)) {
       --x;
       System.out.println("(" + x + "," + (x - k) + ")");
       ret.add(new MatchPair(x, x - k));
      }
      k = k1;
      x = x1;

     } while (--D >= 0);

     Collections.reverse(ret);
     return (MatchPair[]) ret.toArray(new MatchPair[0]);
    }
   }
   pre = cur;

  }
  return null;
 }

 public static MatchPair[] LCS_DN_refined(String[] txt1, String[] txt2) {
  ArrayList list = new ArrayList();

  int M = txt1.length;
  int N = txt2.length;
  int MAX = M + N;

  int[] cur = null;
  int[] pre = new int[1];

  pre[0] = 0;

  int x, y;
  for (int D = 0; D <= MAX; ++D) {
   list.add(pre);
   cur = new int[D + 1];

   for (int k = -1 * D; k <= D; k += 2) {
    if (k == -1 * D
      || k != D
      && pre[(k - 1 + D - 1) >> 1] < pre[(k + 1 + D - 1) >> 1]) {
     x = pre[(k + 1 + D - 1) >> 1];
    } else {
     x = pre[(k - 1 + D - 1) >> 1] + 1;
    }
    y = x - k;
    while (x < txt1.length && y < txt2.length
      && txt1[x].equals(txt2[y])) {
     ++x;
     ++y;
    }
    cur[(k + D) >> 1] = x;

    if (x == txt1.length && y == txt2.length) {
     int x1, k1;
     ArrayList ret = new ArrayList();

     do {
      pre = (int[]) list.get(D);
      if (k == -1 * D
        || k != D
        && pre[(k - 1 + D - 1) >> 1] < pre[(k + 1 + D - 1) >> 1]) {
       x1 = pre[(k + 1 + D - 1) >> 1];
       k1 = k + 1;
      } else {
       x1 = pre[(k - 1 + D - 1) >> 1];
       k1 = k - 1;
      }

      while (x > x1 && (x - k) > (x1 - k1)) {
       --x;
       System.out.println("(" + x + "," + (x - k) + ")");
       ret.add(new MatchPair(x, x - k));
      }
      k = k1;
      x = x1;

     } while (--D >= 0);

     Collections.reverse(ret);
     return (MatchPair[]) ret.toArray(new MatchPair[0]);
    }
   }

   pre = cur;

  }
  return null;
 }
}