LCSUtil.java

package cn.wisenergy.chnmuseum.party.common.util;

import java.util.LinkedList;
import java.util.List;

/**
 * Find LCS(Longest Common Substring) of N strings (N>=2)
 * <p>
 * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/)
 * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php)
 * </p>
 *
 * @author ljs
 * 2011-06-29
 */
public class LCSUtil {

    private static class SuffixNode {
        private String key;
        private List<SuffixNode> children = new LinkedList<>();

        //use "#" for terminal char
        private boolean terminal;

        public SuffixNode() {
            this.key = "";
        }

        public SuffixNode(String key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return this.key + (this.terminal ? "#" : "") + "(" + children.size() + ")";
        }

    }

    private SuffixNode root;
    private final String text;
    //terminators should be ordered according to input strings
    private final char[] terminators;

    public LCSUtil(String text, char[] terminators) {
        this.text = text;
        this.terminators = terminators;
    }

    private void insert(SuffixNode currNode, String key, int startIndex) throws Exception {
        boolean done = false;
        for (int i = 0; i < currNode.children.size(); i++) {
            SuffixNode child = currNode.children.get(i);

            //use min(child.key.length, key.length)
            int len = Math.min(child.key.length(), key.length());
            int j = 0;
            for (; j < len; j++) {
                if (key.charAt(j) != child.key.charAt(j)) {
                    break;
                }
            }
            if (j == 0) {
                //this child doesn't match	any character with the new key
                //order keys by lexi-order
                if (key.charAt(0) < child.key.charAt(0)) {
                    //e.g. child="e" (currNode="abc")
                    //	   abc                     abc
                    //    /  /    =========>      / | /
                    //   e    f   insert "c"     c# e  f

                    SuffixNode node = new SuffixNode(key);
                    currNode.children.add(i, node);
                    node.terminal = true;
                    done = true;
                    break;
                }
            } else {
                //current child's key partially matches with the new key; 0<j<=len
                if (j == len) {
                    if (key.length() == child.key.length()) {
                        if (child.terminal) {
                            throw new Exception("Duplicate Key is found when insertion!");
                        } else {
                            //e.g. child="ab"
                            //	   ab                    ab#
                            //    /  /    =========>    /   /
                            //   e    f   insert "ab"  e     f
                            child.terminal = true;
                        }
                    } else if (key.length() > child.key.length()) {
                        //e.g. child="ab#"
                        //	   ab#                    ab#
                        //    /  /    ==========>    / | /
                        //   e    f   insert "abc"  c# e  f
                        String subkey = key.substring(j);
                        //recursion
                        insert(child, subkey, startIndex + j);
                    } else { //key.length()<child.key.length()
                        //e.g. child="abc#"
                        //	   abc#                      ab#
                        //    /   /      =========>      /
                        //   e     f     insert "ab"    c#
                        //					           /  /
                        //                            e    f
                        String childSubkey = child.key.substring(j); //c
                        SuffixNode subChildNode = new SuffixNode(childSubkey);
                        subChildNode.terminal = child.terminal;
                        subChildNode.children = child.children; //inherited from parent

                        child.key = key;  //ab
                        child.terminal = true;  //ab#

                        child.children = new LinkedList<>();
                        child.children.add(subChildNode);
                    }
                } else {//0<j<len
                    //e.g. child="abc#"
                    //	   abc#                     ab
                    //    /  /     ==========>     / /
                    //   e    f   insert "abd"    c#  d#
                    //                           /  /
                    //                          e    f
                    //split at j
                    String childSubkey = child.key.substring(j);  //c
                    String subkey = key.substring(j); //d

                    SuffixNode subChildNode = new SuffixNode(childSubkey);
                    subChildNode.terminal = child.terminal;
                    subChildNode.children = child.children; //inherited from parent

                    //update child's key
                    child.key = child.key.substring(0, j);
                    //child is not terminal now due to split, it is inherited by subChildNode
                    child.terminal = false;

                    //Note: no need to merge subChildNode

                    SuffixNode node = new SuffixNode(subkey);
                    node.terminal = true;
                    child.children = new LinkedList<>();
                    if (subkey.charAt(0) < childSubkey.charAt(0)) {
                        child.children.add(node);
                        child.children.add(subChildNode);
                    } else {
                        child.children.add(subChildNode);
                        child.children.add(node);
                    }
                }
                done = true;
                break;
            }
        }
        if (!done) {
            SuffixNode node = new SuffixNode(key);
            node.terminal = true;
            currNode.children.add(node);
        }
    }

    public void insert(String suffix, int startIndex) throws Exception {
        if (suffix == null || suffix.length() == 0) {
            return;
        }

        if (root == null) {
            root = new SuffixNode();
        }
        insert(root, suffix, startIndex);
    }

    //build a suffix-tree for a string of text
    public void buildSuffixTree() throws Exception {
        for (int i = 0; i < text.length(); i++) {
            this.insert(text.substring(i), i);
        }
    }

    //for test purpose only
    public void printTree() {
        this.print(0, this.root);
    }

    private void print(int level, SuffixNode node) {
        for (int i = 0; i < level; i++) {
            System.out.format(" ");
        }
        System.out.format("|");
        for (int i = 0; i < level; i++) {
            System.out.format("-");
        }
        if (node.terminal) {
            System.out.format("%s#%n", node.key);
        } else {
            System.out.format("%s%n", node.key);
        }
        for (SuffixNode child : node.children) {
            print(level + 1, child);
        }
    }

    public String findLCS() {
        return findLCS(root);
    }

    //return the longest substring starting with current node (but not including currNode.key)
    private String findLCS(SuffixNode currNode) {
        int maxDepth = currNode.key.length();
        int currDepth = currNode.key.length();

        String longestSubstrSuffix = "";

        for (int i = 0; i < currNode.children.size(); i++) {
            SuffixNode child = currNode.children.get(i);
            if (!child.terminal) {
                int depth = currDepth + child.key.length();

                //terminators are unique, so terminal child is excluded
                boolean containsTerminators = containTerminators(child);
                if (containsTerminators) {
                    if (depth > maxDepth) {
                        maxDepth = depth;
                        longestSubstrSuffix = child.key;
                    }

                    String longestChildSubstrSuffix = findLCS(child);
                    if (longestChildSubstrSuffix.length() > 0) { //not a part of LCS if longestChildSubstrSuffix's lenght is 0
                        int maxChildDepth = longestChildSubstrSuffix.length() + depth;
                        if (maxChildDepth > maxDepth) {
                            maxDepth = maxChildDepth;
                            //the substring is relative to currNode
                            longestSubstrSuffix = child.key + longestChildSubstrSuffix;
                        }
                    }
                }
            }
        }


        return longestSubstrSuffix;
    }

    private boolean containTerminators(SuffixNode currNode) {
        boolean[] done = new boolean[terminators.length];
        return containTerminators(currNode, done);
    }

    private boolean containTerminators(SuffixNode currNode, boolean[] done) {
        boolean allDone = false;

        for (int i = 0; i < currNode.children.size(); i++) {
            SuffixNode child = currNode.children.get(i);
            if (child.terminal) {
                //Note: here the order of terminator is important
                for (int j = 0; j < terminators.length; j++) {
                    int pos = child.key.indexOf(terminators[j]);
                    if (pos >= 0) {
                        done[j] = true;
                        break;
                    }
                }
            } else {
                containTerminators(child, done);
            }

            allDone = true;
            for (int j = 0; j < done.length; j++) {
                if (!done[j]) {
                    allDone = false;
                    break;
                }
            }
            if (allDone) {
                break;
            }
        }

        return allDone;
    }

//    public static void main(String[] args) throws Exception {
//        System.out.println("****************************");
//        System.out.format("LCS for 3 strings:{abc,bcabca,aabcf}%n");
//        String text = "abc$bcabca@aabcf%";
//        LCSUtil strie = new LCSUtil(text, new char[]{'$', '@', '%'});
//        strie.buildSuffixTree();
//        //strie.printTree();
//
//        String longestSubstr = strie.findLCS();
//        System.out.format("%s%n", longestSubstr);
//
//
//        System.out.println("****************************");
//        System.out.format("LCS for 3 strings:{abcd,bcca,aabc}%n");
//        text = "abcd$bcca@aabc%";
//        strie = new LCSUtil(text, new char[]{'$', '@', '%'});
//        strie.buildSuffixTree();
//        //strie.printTree();
//
//        longestSubstr = strie.findLCS();
//        System.out.format("%s%n", longestSubstr);
//
//
//        System.out.println("****************************");
//        System.out.format("LCS for 2 strings:{asdfldkjxlfjax123456789abckljddfdfe123456789ees, xsdldkjalfla123456789abcfleur123456789ljafa}%n");
//        text = "asdfldkjxlfjax123456789abckljddfdfe123456789ees$xsdldkjalfla123456789abcfleur123456789ljafa@";
//        strie = new LCSUtil(text, new char[]{'$', '@'});
//        strie.buildSuffixTree();
//        //strie.printTree();
//
//        longestSubstr = strie.findLCS();
//        System.out.format("%s%n", longestSubstr);
//
//        System.out.println("****************************");
//        System.out.format("LCS for 5 strings:{abcd,abce,abd,bdess,ace}%n");
//        text = "abcd$abce@abd%bdess&ace#";
//        strie = new LCSUtil(text, new char[]{'$', '@', '%', '&', '#'});
//        strie.buildSuffixTree();
//        //strie.printTree();
//
//        longestSubstr = strie.findLCS();
//        System.out.format("%s%n", longestSubstr);
//    }
}