/**
* Author: yiminghe
* Date: 2008-10-24
* Time: 15:08:32
* Any problem ,contact [email protected].
*/
import java.io.*;
import java.util.*;
/**
*
*
* LCS ,
*
*/
class LCS {
public static void main(String[] args) throws IOException {
String[] source = {"axybcde", "cdefxy", "xyccde"};
SuffixTreeNode st = buildSuffixTree(source);
String result;
result = Lcs(st.firstChild, source.length);
if (result.equals(""))
System.out.println("No common string!");
else
System.out.println("The longest common substring is : "
+ result + " .");
String[] commons = commonString(source);
System.out.println(Arrays.asList(commons));
}
/**
*
*
* @param ss
* @return
*/
public static SuffixTreeNode buildSuffixTree(String ss[]) {
HashMap<String, String> belong = new HashMap<String, String>();
belong.put("0", "");
SuffixTreeNode SuffixTree =
new SuffixTreeNode(-1, "", 0, belong);
//Add suffixs...
for (int i = 0; i < ss.length; i++) {
System.err.print(" [" + (i + 1) + "]");
belong = new HashMap<String, String>();
belong.put("" + (i + 1), "");
for (int index = 0; index < ss[i].length(); index++) {
String str = ss[i].substring(index);
SuffixTree.insert(index, str, 0, belong);
}
System.err.println(" - OK");
}
return SuffixTree;
}
/**
*
*
* @param suffixtree
* @param count
* @return
*/
public static String Lcs(SuffixTreeNode suffixtree, int count) {
String result = "";
String result2;
while (suffixtree != null) {
int flag = suffixtree.belongTo.size();
if (flag == count) {
if (suffixtree.isLeaf()) {
//
if (result.length() <
suffixtree.label.length())
result = suffixtree.label;
} else {
//
result2 = Lcs(suffixtree.firstChild, count);
//
if (result.length() <
(suffixtree.label.length() + result2.length()))
result = suffixtree.label + result2;
}
}
suffixtree = suffixtree.next;
}
return result;
}
/**
* ,
*
* @param source
* @return
*/
public static String[] commonString(String[] source) {
HashSet<String> r = new HashSet<String>();
SuffixTreeNode st = buildSuffixTree(source);
recurCommon(r, st.firstChild, source.length);
String[] original = r.toArray(new String[r.size()]);
ArrayList<String> result = new ArrayList<String>();
for (int i = 0; i < original.length; i++) {
int j = 0;
for (j = 0; j < original.length; j++) {
// ,
if (i != j && original[j].endsWith(original[i])) {
break;
}
}
if (j == original.length) {
result.add(original[i]);
}
}
return result.toArray(new String[result.size()]);
}
// ,
private static boolean recurCommon(HashSet<String> r, SuffixTreeNode suffixtree, int count) {
boolean result = false;
while (suffixtree != null) {
int flag = suffixtree.belongTo.size();
if (flag == count) {
result = true;
if (suffixtree.isLeaf()) {
String re = suffixtree.label;
SuffixTreeNode temp = suffixtree;
while (temp.parent != null) {
temp = temp.parent;
re = temp.label + re;
}
r.add(re);
} else {
//
boolean has = recurCommon(r, suffixtree.firstChild, count);
//
if (!has) {
String re = suffixtree.label;
SuffixTreeNode temp = suffixtree;
while (temp.parent != null) {
temp = temp.parent;
re = temp.label + re;
}
r.add(re);
}
}
}
suffixtree = suffixtree.next;
}
return result;
}
}
class SuffixTreeNode {
//
//
int index;
//
String label;
//
SuffixTreeNode next;
//
SuffixTreeNode firstChild = null;
//
SuffixTreeNode parent = null;
//
int level;
//
HashMap<String, String> belongTo = null;
SuffixTreeNode(int i, String s,
int level, HashMap<String, String> flag) {
this.index = i;
this.label = s;
this.level = level;
if (belongTo == null)
belongTo = new HashMap<String, String>();
//Put subject-to information to belongTo...
belongTo.putAll(flag);
}
void setChilden(SuffixTreeNode n) {
this.firstChild = n;
if (n != null)
n.parent = this;
}
boolean isLeaf() {
return (this.firstChild == null);
}
/**
*
*
* @param ind index
* @param str insert_str
* @param level level
* @param belong belong
*/
public void insert(int ind, String str,
int level, HashMap<String, String> belong) {
SuffixTreeNode newnode, firstChild, prev;
String strtemp, prefix;
int index_i;
//
if (this.isLeaf()) {
newnode = new SuffixTreeNode(ind, str,
level + 1, belong);
this.setChilden(newnode);
return;
}
firstChild = this.firstChild;
if (firstChild.label.charAt(0) > str.charAt(0)) {
newnode = new SuffixTreeNode(ind, str,
level + 1, belong);
this.setChilden(newnode);
newnode.next = firstChild;
return;
}
prev = firstChild;
//
while ((firstChild != null) &&
(firstChild.label.charAt(0) <
str.charAt(0))) {
prev = firstChild;
firstChild = firstChild.next;
}
if (firstChild == null) {
newnode = new SuffixTreeNode(ind, str,
level + 1, belong);
newnode.parent = this;
prev.next = newnode;
return;
}
if (firstChild.label.charAt(0) > str.charAt(0)) {
newnode = new SuffixTreeNode(ind, str,
level + 1, belong);
prev.next = newnode;
newnode.parent = this;
newnode.next = firstChild;
return;
}
// str
if (str.equals(firstChild.label)) {
//
firstChild.belongTo.putAll(belong);
return;
}
//
int minLength = Math.min(firstChild.label.length(), str.length());
for (index_i = 1; index_i < minLength; index_i++) {
if (firstChild.label.charAt(index_i) !=
str.charAt(index_i)) {
break;
}
}
//temp ， str
if (index_i == firstChild.label.length()) {
//str temp
strtemp = str.substring(index_i);
firstChild.insert(ind, strtemp, level + 1, belong);
//
firstChild.belongTo.putAll(belong);
return;
}
//str , temp
// temp
prefix = firstChild.label.substring(0, index_i);
strtemp = firstChild.label.substring(index_i);
// temp str
prev = new SuffixTreeNode(firstChild.index, strtemp,
level + 1, firstChild.belongTo);
prev.setChilden(firstChild.firstChild);
firstChild.setChilden(prev);
firstChild.index = -1;
firstChild.label = prefix;
firstChild.belongTo.putAll(belong);
prev.lowDown();
// str temp
if (index_i < str.length()) {
strtemp = str.substring(index_i);
firstChild.insert(ind, strtemp, level + 1, belong);
}
}
void print() {
}
/**
* ，
*/
void lowDown() {
SuffixTreeNode temp;
this.level++;
if (this.isLeaf())
return;
temp = this.firstChild;
while (temp != null) {
temp.lowDown();
temp = temp.next;
}
}
}