package DynamicProgramming;
public class LCS {
public static enum Direction {
H, V, O;
};
public class Paire {
public int cal;
public Direction d;
public Paire(int cal, Direction d) {
this.cal = cal;
this.d = d;
}
public Paire() {
this.cal = 0;
}
@Override
public String toString() {
return cal + "-" + d;
}
}
Paire[][] p;
String u, v;
public LCS(String u, String v) {
this.u = u;
this.v = v;
p = new Paire[u.length() + 1][v.length() + 1];
for (int i = 0; i < u.length() + 1; i++) {
for (int j = 0; j < v.length() + 1; j++) {
p[i][j] = new Paire();
}
}
}
public void init() {
for (int i = 1; i < u.length() + 1; i++) {
for (int j = 1; j < v.length() + 1; j++) {
if (u.charAt(i - 1) == v.charAt(j - 1)) {
p[i][j].cal = 1 + p[i - 1][j - 1].cal;
p[i][j].d = Direction.O;
} else if (p[i - 1][j].cal > p[i][j - 1].cal) {
p[i][j].cal = p[i - 1][j].cal;
p[i][j].d = Direction.V;
} else {
p[i][j].cal = p[i][j - 1].cal;
p[i][j].d = Direction.H;
}
}
}
}
public String result(int i, int j) {
if (p[i][j].cal == 0) {
return "";
}
if (p[i][j].d == Direction.O) {
return result(i - 1, j - 1) + u.charAt(i - 1);
}
if (p[i][j].d == Direction.H) {
return result(i, j - 1);
}
return result(i - 1, j);
}
public static String run(String u, String v){
LCS app = new LCS(u,v);
app.init();
return app.result(u.length(), v.length());
}
public void print() {
System.out.print("\t\t");
for (int i = 1; i < v.length() + 1; i++) {
System.out.print(v.charAt(i - 1) + "\t");
}
System.out.println("");
for (int i = 0; i < u.length() + 1; i++) {
if (i == 0) {
System.out.print("\t");
} else {
System.out.print(u.charAt(i - 1) + "\t");
}
for (int j = 0; j < v.length() + 1; j++) {
System.out.print(p[i][j] + "\t");
}
System.out.println("");
}
}
public static String doYouMean(String query, String[] text){
String result[] = new String[text.length];
for (int i = 0; i < text.length; i++) {
result[i] = LCS.run(query, text[i]);
}
int max = 0;
for (int i = 1; i < result.length; i++) {
if(result[max].length() < result[i].length())
max = i;
}
return text[max];
}
public static void main(String[] args) {
System.out.println(LCS.run("abcdbdab","bdcaba" ));
String dbText[] = new String[]{"house of cards", "game of throne", "breaking bad"};
System.out.println("Do you mean " + LCS.doYouMean("ga of Zrone", dbText));
}
}