두 문자열의 모든 공통 부분 시퀀스를 식별하는 알고리즘

Question

주어진 두 문자열의 모든 하위 시퀀스를 식별해야합니다. 가장 긴 공통 서브 시퀀스는 가장 긴 서브 시퀀스 만 식별합니다. 그러나 여기서 모든 임계 값을 초과하는 서브 시퀀스를 원합니다. 특정 알고리즘이나 접근법? 아래의 임계 값이 2 인 경우,이

Julie loves me more than Linda loves me 
Jane likes me more than Julie loves me 

같은

뭔가

me more than 
loves me 

Answer 1

Set<String> allCS;//create an empty set 
String[] subStrings = getSubSequences(string2); //find the subsequence of string2(smaller string) 
for (String str : subStrings) { 
    String lcs = LCS(string1, str); 
    if(lcs.length > THRESHOLD) { 
     allCS.put(lcs); 
    } 
} 

여기서 모든 서브 getSubSequences(String s) 복귀 이들 2 개 스트링의 공통 서브 서열이다 주어진 문자열 매개 변수의 은 s1 및 s2의 LCS를 반환합니다.

getSubSequences(String s)은 비트 마스크 방식 또는 재귀 적으로 구현할 수 있습니다.

LCS(String s1, String s2)은 O(n^2) 동적 프로그래밍 방식을 사용하여 구현할 수 있으며 나중에 가장 긴 하위 시퀀스 b 문자열을 인쇄하기 위해 DP 테이블의 경로를 역 추적 할 수 있습니다.

2^length(string) - 1 하위 시퀀스가 ​​가능하기 때문에 더 작은 문자열이 꽤 길면 효율적이지 않습니다.

Answer 2

이것은 알고리즘 질문이므로 언어는 중요하지 않습니다. 내 접근 방식은이 두 문자열 사이의 모든 서브 시퀀스를 생성하고 임계 값을 초과하는 서브 시퀀스를 찾습니다.

파이썬 코드 (자바가 훨씬 더 어려울 안) :

def common_subsequences(a, b, threshold): 
    # tokenize two string (keep order) 
    tokens_a = a.split() 
    tokens_b = b.split() 
    # store all common subsequences 
    common = set() 
    # with each token in a 
    for i, token in enumerate(tokens_a): 
     # if it also appears in b 
     # then this should be a starting point for a common subsequence 
     if token in tokens_b: 
      # get the first occurence of token in b 
      # and start from there 
      j = tokens_b.index(token) 
      k = i 
      temp = token 
      # since we need all subsequences, we get length-1 subsequences too 
      common.add(temp) 
      # while still have token in common 
      while j < len(tokens_b) and k < len(tokens_a): 
       if j + 1 < len(tokens_b) and k + 1 < len(tokens_a) and tokens_b[j+1] == tokens_a[k+1]: 
        temp += " " + tokens_b[j+1] 
        j += 1 
        k += 1 
        # adding (new) common subsequences 
        common.add(temp) 
       # or else we break 
       else: 
        break 
    # we only get the ones having length >= threshold 
    return [s for s in common if len(s.split()) >= threshold] 

a = "Julie loves me more than Linda loves me" 
b = "Jane likes me more than Julie loves me" 
print common_subsequences(a, b, 2) 

모든 common_subsequences :

set(['me', 'more than', 'Julie', 'Julie loves', 'Julie loves me', 'me more', 'loves', 'more', 'than', 'me more than', 'loves me']) 

common_subsequences> = 임계 값 :

['more than', 'Julie loves', 'Julie loves me', 'me more', 'me more than', 'loves me']