Java implementation for the longest common substring of n lines

Question

I need to find the longest common substring of n lines and use the result in my project.

Is there any existing implementation / library in java that already does this?

Thanks for your answers in advance.

Answer 1

We can use the code below to determine the longest common substring of n lines

public static String identifyCommonSubStrOfNStr(String [] strArr){ String commonStr=""; String smallStr =""; //identify smallest String for (String s :strArr) { if(smallStr.length()< s.length()){ smallStr=s; } } String tempCom=""; char [] smallStrChars=smallStr.toCharArray(); for (char c: smallStrChars){ tempCom+= c; for (String s :strArr){ if(!s.contains(tempCom)){ tempCom=c; for (String s :strAarr){ if(!s.contains(tempCom)){ tempCom=""; break; } } break; } } if(tempCom!="" && tempCom.length()>commonStr.length()){ commonStr=tempCom; } } return commonStr; } 

Answer 2

What about concurrent-trees ?

This is a small library (~ 100KB) available at Maven Central. The algorithm uses a combination of Radix and Suffix trees. It is known that linear time complexity ( wikipedia ).

 public static String getLongestCommonSubstring(Collection<String> strings) { LCSubstringSolver solver = new LCSubstringSolver(new DefaultCharSequenceNodeFactory()); for (String s: strings) { solver.add(s); } return solver.getLongestCommonSubstring().toString(); } 

Answer 3

This page pretty accurately gives what you want in several languages.

 public static int longestSubstr(String first, String second) { if (first == null || second == null || first.length() == 0 || second.length() == 0) { return 0; } int maxLen = 0; int fl = first.length(); int sl = second.length(); int[][] table = new int[fl][sl]; for (int i = 0; i < fl; i++) { for (int j = 0; j < sl; j++) { if (first.charAt(i) == second.charAt(j)) { if (i == 0 || j == 0) { table[i][j] = 1; } else { table[i][j] = table[i - 1][j - 1] + 1; } if (table[i][j] > maxLen) { maxLen = table[i][j]; } } } } return maxLen; } 

Answer 4

Well, you can try to expand the Wikipedia version ( http://en.wikipedia.org/wiki/Longest_common_substring_problem ) for n lines by putting it in a loop that iterates over all of your lines.