求最长公共子序列

问题

给出两个字符串，求出它们之中相对顺序相同，字符相同的最长的公共子序列。

用法

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        String string0 = "abcicba";
        String string1 = "abdkscab";
        System.out.println(Solution.findLongestSubsequence(string0,string1));
    }
}

输出

解集:
1 1 1 1 1 1 1 1 
1 2 2 2 2 2 2 2 
1 2 2 2 2 3 3 3 
1 2 2 2 2 3 3 3 
1 2 2 2 2 3 3 3 
1 2 2 2 2 3 3 4 
1 2 2 2 2 3 4 4 
最长公共子序列长度为:4
倒序输出最长子序列:ab<>c<>a

Process finished with exit code 0

代码实现

package com.company;

public class Solution {
    /**
     * 查找两个字符串的最长公共子序列。
     * 所谓最长公共子序列，需要满足两个条件。
     * 1、它包含的字符相同。
     * 2、相对顺序相同。
     * 最长公共子序列并不是最长公共子串
     * 二者的区别很大。
     * 很简单如果矩阵对应的两个字符不相等，该单元格的值就等于它上面的和左边的较大的单元格的值。
     * 如果相等，就等于左上角单元格的值+1。
     * 本问题需要输出那个子序列，这个有点麻烦，从解集可以看出来
     * 不一定相等就是最长公共子序列的开始。
     * 所以用单链表的回溯法可以打印出最长公共子序列。
     * 把其中重复的结点合并作为间隔符<>来显示
     * @param string0
     * @param string1
     * @return
     */
    static public String findLongestSubsequence(String string0,String string1) {
        if (string0.length() == 0 || string1.length() == 0)return "";
        SingleLinker[][] answerArray = new SingleLinker[string0.length()][string1.length()];
        for (int counter = 0;counter < string0.length();counter++) {
            for (int counter0 = 0;counter0 < string1.length();counter0++) {
                answerArray[counter][counter0] = new SingleLinker(counter,counter0);
                if (string0.charAt(counter) == string1.charAt(counter0)) {
                    if (counter - 1 >= 0 && counter0 - 1 >= 0) {
                        answerArray[counter][counter0].setEqualCounter(answerArray[counter - 1][counter0 - 1].getEqualCounter() + 1);
                        answerArray[counter][counter0].prePointer = answerArray[counter - 1][counter0 - 1];
                    }
                    else answerArray[counter][counter0].setEqualCounter(1);
                }
                else {
                    if (counter - 1 >= 0 && counter0 - 1 < 0) {
                        answerArray[counter][counter0].setEqualCounter(answerArray[counter - 1][counter0].getEqualCounter());
                        answerArray[counter][counter0].prePointer = answerArray[counter - 1][counter0];
                    }
                    else if (counter - 1 < 0 && counter0 - 1 >= 0) {
                        answerArray[counter][counter0].setEqualCounter(answerArray[counter][counter0 - 1].getEqualCounter());
                        answerArray[counter][counter0].prePointer = answerArray[counter][counter0 - 1];
                    }
                    else if (counter - 1 < 0 && counter0 - 1 < 0)
                        answerArray[counter][counter0].setEqualCounter(0);
                    else {
                        if (answerArray[counter - 1][counter0].getEqualCounter() > answerArray[counter][counter0 - 1].getEqualCounter()) {
                            answerArray[counter][counter0].setEqualCounter(answerArray[counter - 1][counter0].getEqualCounter());
                            answerArray[counter][counter0].prePointer = answerArray[counter - 1][counter0];
                        } else {
                            answerArray[counter][counter0].setEqualCounter(answerArray[counter][counter0 - 1].getEqualCounter());
                            answerArray[counter][counter0].prePointer = answerArray[counter][counter0 - 1];
                        }
                    }
                }
            }
        }
        System.out.println("解集:");
        for (int counter = 0;counter < string0.length();counter++) {
            for (int counter0 = 0;counter0 < string1.length();counter0++) {
                System.out.print(answerArray[counter][counter0].getEqualCounter() + " ");
            }
            System.out.println();
        }
        System.out.println("最长公共子序列长度为:" + answerArray[string0.length() - 1][string1.length() - 1].getEqualCounter());
        System.out.print("倒序输出最长子序列:");
        SingleLinker currentNode = answerArray[string0.length() - 1][string1.length() - 1];
        SingleLinker[] nodeStack = new SingleLinker[answerArray[string0.length() - 1][string1.length() - 1].getEqualCounter()];
        int nodeStackPointer = -1;
        while (currentNode != null && currentNode.getEqualCounter() > 0) {
            if (nodeStackPointer == -1 || nodeStack[nodeStackPointer].getEqualCounter() != currentNode.getEqualCounter())
                nodeStack[++nodeStackPointer] = currentNode;
            else {
                nodeStack[nodeStackPointer] = currentNode;
                nodeStack[nodeStackPointer].setHasDivider(true);
            }
            currentNode = currentNode.prePointer;
        }
        //逆转单链表
        StringBuilder longestSubsequence = new StringBuilder();
        while (nodeStackPointer > -1) {
            longestSubsequence.append(string0.charAt(nodeStack[nodeStackPointer].getX()));
            if (nodeStack[nodeStackPointer].isHasDivider() && nodeStackPointer != 0)longestSubsequence.append("<>");
            nodeStackPointer--;
        }
        return longestSubsequence.toString();
    }
}

package com.company;

public class SingleLinker {
    private int x = -1;
    private int y = -1;
    private int equalCounter = 0;
    private boolean hasDivider = false;
    public SingleLinker prePointer = null;

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

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getEqualCounter() {
        return equalCounter;
    }

    public void setEqualCounter(int equalCounter) {
        this.equalCounter = equalCounter;
    }

    public boolean isHasDivider() {
        return hasDivider;
    }

    public void setHasDivider(boolean hasDivider) {
        this.hasDivider = hasDivider;
    }
}