알고리즘 - 반복 인수를 기반으로하는 문자열 일치

Question

입력 (A, B, C)으로 3 개의 문자열이 있습니다. = "WORD"

A = "SLOVO", B, C =

그리고 문자열 C는 무한 repetiton 문자열 A와 B를 연결 한 경우 나, 결정 알고리즘을 찾을 필요 반복 예 : A^2 = "SLOVOSLOVO"이고 문자열 C에서 "SLOVOSLOVO"의 처음 8 글자 "SLOVOSLO"입니다. 문자열 B도 비슷합니다. 알고리즘에 대한

내 생각 : 알고리즘의

index_A = 0; //index of actual letter of string A 
index_B = 0; 

Go throught the hole string C from 0 to size(C) 
{ 
    Pick the actual letter from C (C[i]) 
    if(C[i] == A[index_A] && C[i] != B[index_B]) 
    { 
    index_A++; 
    Go to next letter in C 
    } 
    else if(C[i] == B[index_B] && C[i] != A[index_A]) 
    { 
    index_B++; 
    Go to next letter in C 
    } 
    else if(C[i] == B[index_B] && C[i] == A[index_A]) 
    { 
    Now we couldn´t decice which way to go, so we should test both options (maybe recusrsion) 
    } 
    else 
    { 
    return false; 
    } 
} 

오기 '만을 간략 설명하지만 난 당신이해야 할이 알고리즘의 주요 아이디어를 이해하는데 도움이되기를 바랍니다. 이 문제를 해결하는 방법이 좋은가요? 더 나은 해결책이 있습니까? 아니면 몇 가지 팁?

Answer 1

기본적으로 모든 정규 표현식 정규 표현식에 문제가 있습니다. 예, 두 옵션을 모두 테스트해야하며 작동하지 않으면 다른 옵션에 backtrack을 입력해야합니다. 재귀 적으로 문자열에 대한 루프를 표현하면 여기에서 도움이 될 수 있습니다.

그러나 동시에 두 옵션을 모두 시도 할 수있는 방법이 있습니다. 이 아이디어에 대한 인기있는 기사 Regular Expression Matching Can Be Simple And Fast을 참조하십시오. 반복적으로 두 문자열에서 가능한 모든 위치를 추적합니다 (c). 필요한 룩업 구조는 무한 반복 문자열에 위치를 저장하는 대신 문자열 위치에 모듈러스를 사용할 수 있으므로 크기는 len(A)*len(B)입니다.

// some (pythonic) pseudocode for this: 

isIntermixedRepetition(a, b, c) 
    alen = length(a) 
    blen = length(c) 
    pos = new Set() // to store tuples 
        // could be implemented as bool array of dimension alen*blen 
    pos.add([0,0]) // init start pos 
    for ci of c 
     totest = pos.getContents() // copy and 
     pos.clear()    // empty the set 
     for [indexA, indexB] of totest 
      if a[indexA] == ci 
       pos.add([indexA + 1 % alen, indexB]) 
      // no else 
      if b[indexB] == ci 
       pos.add([indexA, indexB + 1 % blen]) 
     if pos.isEmpty 
      break 
    return !pos.isEmpty