효율적

Question

은 길이 N의 시퀀스 주어진 일반적인 문자열을 결정하는 상기 서열의 내부 문자열 A, B, C, D

Input: Seq={ACCBADBAACCBACADAAADC...DBACDBACD} 
Output: string appear most of the time 

문자열을 찾기 위해 어떠한 빠른 알고리즘이 대부분의 시간에 표시된다 ? 어떤 의미입니까

예 : AAA는 한 번만 Seq에 나타나고, BAA도 한 번 표시되는 것처럼 말하게하십시오 ... 그 다음에 ACCBA가 발견 된 후 Seq에 2 번 나타나는 문자열이 대부분입니다. 시간은 출력이 ACCBA.state 알고리즘의 최악의 경우의 복잡도이기도합니다 ...

이것은 무차별 대입과 같은 많은 답변을 가지고있을 수 있지만 매우 느립니다 ... 필요가 없습니다 정확한 코드를 제공하십시오 ... psedo 코드가 충분해야합니다 ... 몇 가지 단서 또는 참조 정보를 제공하는 데 도움주세요 ... 자세히 알고 싶습니다 ...

Answer 1

이것은 생물 정보학 숙제와 같은 의심스러운 소리입니다. 그럼에도 불구하고 suffix trees을 확인하십시오.

Answer 2

동일한 문자로 구성된 가장 긴 문자열을 찾으려면 비교적 간단한 알고리즘을 사용하여 선형 시간으로 수행 할 수 있다고 생각합니다. 기본적으로 현재 가장 긴 시퀀스 문자, 카운트, 마지막으로 본 문자 및 연속적으로 문자가 표시된 횟수를 추적합니다. 값을 스캔하고 업데이트하면됩니다.

Answer 3

두 가지 해석을 볼 수 있습니다. 내가 가장 먼저 생각하는 것을 다루겠다.

문자의 가장 긴 하위 시퀀스를 계산하여 어떤 하위 시퀀스가 ​​가장 많이 발생하는지 확인하려는 경우입니다. 즉, 문자열 AAABBBBBAAA은 {2,AAA}을 제공합니다. 왜냐하면 가장 긴 서브 시퀀스 중 두 개가 있고 BBBBB 중 하나만 있기 때문입니다.

그렇게하기 위해서는, 당신은 사용할 수 있습니다 : 당신이 다른 문자의 일정한 수 (D-A)를 가지고 있기 때문에 이것은 당신에게 O (n)의 저장 및 O (n)의 시간을 줄 것이다

dim seqcount['A'..'D',1..len(str)] = 0 # Array to hold counts. 
lastch = str[0]       # Last character processed. 
count = 1        # Count of last char processed. 
maxseqcount = 0       # Largest quantity to date. 
maxseqchars = ""       # Letters of that largest quantity. 

# Process the end of a sequence. 

def endseq (thisch,thiscount): 
    # Increase quantity for letter/length combo. 

    seqcount[thisch,thiscount] = seqcount[thisch,thiscount] + 1 

    # Quantity same as current max, add letter to list (if not already there). 

    if seqcount[thisch,thiscount] == maxseqcount: 
     if not maxseqchars.contains (thisch): 
      maxseqchars = maxseqchars + thisch 

    # Quantity greater than current max, change max and use this letter. 

    if seqcount[thisch,thiscount] > maxseqcount: 
     maxseqcount = seqcount[thisch,thiscount] 
     maxseqchars = thisch 

def main: 
    # Process every character (other than first) once. 

    for pos = 1 to len(str) - 1: 
     # Still in a sequence, add to length and restart loop. 

     if str[pos] == lastch: 
      count = count + 1 
      continue 

     # Letter change, process end of sequence. 

     endseq (lastch, count) 

     # Then store this new character and re-init count. 

     lastch = str[pos] 
     count = 1 

    # Termination, we still have the last sequence to deal with. 

    endseq (lastch, count) 

문자열의 각 문자를 한 번만 처리하는 것입니다. 처리의 끝에서

, 당신은 당신의 입력 문자열이 {2,A} 및 {2,B} 모두 동일하게 유효하다는 것을 의미 ABAB 같은 수 있기 때문에 maxseqchars은 반드시 단일 문자 아니지만 당신이 {maxseqcount,maxseqchars}으로 원하는 것을 얻을 수 있습니다.

---

두 번째 (가능성이 있지만) 가능성

는 가장 발생 순서가 {1,whatever single character occurs the most in the string} 될 것입니다 경우에 단일 문자의 긴 시퀀스를 사용할 필요가 없다는 것입니다.

시퀀스가 ​​모두 동일한 문자가 아니며,이 후자의 가능성이 해당 될 수 있습니다 (동일한 문자 또는 임의의 문자의 임의의 길이 허용).

그렇다면 모든 문자를 O (n)로 처리하여 어느 한 문자가 가장 많이 나오는 지 확인하십시오. 다음은 단순히 그 문자의 길이 = 1 시퀀스입니다.

예를 들어 문자열이 인 경우 {1,ACCBA}은 이 아니고 해결책입니다. 오히려, 그것은 {2,A} ot {2,C}입니다.