문자열에서 가장 긴 유사한 서브 시퀀스를 찾으십시오.

Question

서브 시퀀스의 첫 번째 절반이 두 번째 절반과 동일하도록 가장 긴 서브 시퀀스를 찾고 싶다고 가정 해보십시오.

예 : 문자열 abkcjadfbck에서 abcabc는 첫 번째와 두 번째 절반에서 반복되므로 결과는 abcabc입니다. 교반에 aaa 결과는 aa입니다.

Answer 1

이 작업은 잘 알려진 두 가지 문제의 조합으로 간주 될 수 있습니다.

1. 두 시퀀스 사이의 일부 지점을 미리 알고 있다면 두 문자열에 가장 잘 맞는 것을 찾아야합니다. 이것은 Pairwise alignment 문제입니다. 다양한 동적 프로그래밍 방법으로 O (N) 시간에이를 해결합니다.
2. 문자열을 최적으로 분할해야하는 지점을 찾으려면 Golden section search 또는 피보나치 검색을 사용할 수 있습니다. 이러한 알고리즘은 O (log N) 시간의 복잡성을 갖습니다.

Answer 2

inputString을 통한 첫 번째 전달에서 각 문자가 발생하는 빈도를 계산하고 발생 빈도가있는 문자를 제거 할 수 있습니다.

input: inputString 
data strucutres: 
Set<Triple<char[], Integer, Integer>> potentialSecondWords; 
Map<Char, List<Integer>> lettersList; 

for the characters c with increasing index h in inputString do 
    if (!lettersList.get(c).isEmpty()) { 
    for ((secondWord, currentIndex, maxIndex) in potentialSecondWords) { 
     if (there exists a j in lettersList.get(c) between currentIndex and maxIndex) { 
     update (secondWord, currentIndex, maxIndex) by adding c to secondWord and replacing currentIndex with j; 
     } 
    } 
    if potentialSecondWords contains a triple whose char[] is equal to c, remove it; 
    put new Triple with value (c,lettersList.get(c).get(0), h-1) into potentialSecondWords; 
    } 
    lettersList.get(c).add(h); 
} 
find the largest secondWord in potentialSecondWords and output secondWord twice; 

그래서이 알고리즘은 의미가 각 인덱스, 현재 인덱스에서 시작하여 잠재적 인 두 번째 단어를 나타내는 트리플에 대한 생성, 배열을 통해 한 번 통과하고, 모든 잠재적 인 두 번째 단어를 업데이트합니다.

적절한 목록 구현 및 n이 inputString의 크기 인 경우이 알고리즘은 최악의 런타임 O (n²)를가집니다.^n.