@Test public void testLcs() throws Exception { assertEquals("", LongestCommonSubstring.lcs("a", "node")); assertEquals("ma", LongestCommonSubstring.lcs("markus", "mama")); assertEquals("mar", LongestCommonSubstring.lcs("markus döring", "carla maria möglich")); }
public static String lcs(String text1, String text2) { int N1 = text1.length(); String text = text1 + '\1' + text2; int N = text.length(); SuffixArray suffix = new SuffixArray(text); String lcs = ""; for (int i = 1; i < N; i++) { if (suffix.index(i) < N1 && suffix.index(i - 1) < N1) continue; if (suffix.index(i) > N1 && suffix.index(i - 1) > N1) continue; int length = suffix.lcp(i); if (length > lcs.length()) { lcs = text.substring(suffix.index(i), suffix.index(i) + length); } } return lcs; }
LongestCommonSubstring { public static String lcs(String text1, String text2) { int N1 = text1.length(); String text = text1 + '\1' + text2; int N = text.length(); SuffixArray suffix = new SuffixArray(text); String lcs = ""; for (int i = 1; i < N; i++) { if (suffix.index(i) < N1 && suffix.index(i - 1) < N1) continue; if (suffix.index(i) > N1 && suffix.index(i - 1) > N1) continue; int length = suffix.lcp(i); if (length > lcs.length()) { lcs = text.substring(suffix.index(i), suffix.index(i) + length); } } return lcs; } }
LongestCommonSubstring { public static String lcs(String text1, String text2) { int N1 = text1.length(); String text = text1 + '\1' + text2; int N = text.length(); SuffixArray suffix = new SuffixArray(text); String lcs = ""; for (int i = 1; i < N; i++) { if (suffix.index(i) < N1 && suffix.index(i - 1) < N1) continue; if (suffix.index(i) > N1 && suffix.index(i - 1) > N1) continue; int length = suffix.lcp(i); if (length > lcs.length()) { lcs = text.substring(suffix.index(i), suffix.index(i) + length); } } return lcs; }  }
LongestCommonSubstring { public static String lcs(String text1, String text2) { int N1 = text1.length(); String text = text1 + '\1' + text2; int N = text.length(); SuffixArray suffix = new SuffixArray(text); String lcs = ""; for (int i = 1; i < N; i++) { if (suffix.index(i) < N1 && suffix.index(i - 1) < N1) continue; if (suffix.index(i) > N1 && suffix.index(i - 1) > N1) continue; int length = suffix.lcp(i); if (length > lcs.length()) { lcs = text.substring(suffix.index(i), suffix.index(i) + length); } } return lcs; }  static String lcs(String text1, String text2); }
LongestCommonSubstring { public static String lcs(String text1, String text2) { int N1 = text1.length(); String text = text1 + '\1' + text2; int N = text.length(); SuffixArray suffix = new SuffixArray(text); String lcs = ""; for (int i = 1; i < N; i++) { if (suffix.index(i) < N1 && suffix.index(i - 1) < N1) continue; if (suffix.index(i) > N1 && suffix.index(i - 1) > N1) continue; int length = suffix.lcp(i); if (length > lcs.length()) { lcs = text.substring(suffix.index(i), suffix.index(i) + length); } } return lcs; }  static String lcs(String text1, String text2);  }