n 개의 문자열 중에서 가장 긴 공통 부분 문자열을위한 Java 구현

Question

n 개의 문자열 중에서 가장 긴 공통 부분 문자열을 찾아 내 프로젝트의 결과를 사용해야합니다.

이미이 작업을 수행하는 java의 기존 구현/라이브러리가 있습니까?

답장을 미리 보내 주셔서 감사합니다.

Answer 1

This 페이지 꽤 많은 언어로 원하는 것을 정확하게 제공합니다.

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 2

그럼 당신은 모든 문자열을 통해 루프에있는 반복 그것을 넣어 n 개의 문자열에 대한 위키 피 디아의 버전 (http://en.wikipedia.org/wiki/Longest_common_substring_problem을) 확장을 시도 할 수 있습니다.

Answer 3

우리는 n 개의 문자열 concurrent-trees에 대한

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 4

무엇의 최장 공통 서브 문자열을 식별하는 코드 아래에 사용할 수 있습니까?

Maven Central에서 사용할 수있는 작은 (~ 100KB) 라이브러리입니다. 알고리즘은 Radix 및 Suffix Trees의 조합을 사용합니다. 어느 것이 선형 시간 복잡도 (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(); 
}