모든 시퀀스

Question

가 발생하지 않도록하는 방법

가능한 중복 :
Square Subsequence

내가 interviewstreet.com에서 "Square Subsequences"문제를 해결하기 위해 노력 해왔다 :

을 문자열은 동일한 문자열의 두 사본을 연결하여 얻을 수있는 경우 정사각형 문자열이라고합니다. 예를 들어 "abab", "aa"는 정사각형 문자열이며 "aaa", "abba"는 그렇지 않습니다.

주어진 문자열에서 문자열의 하위 시퀀스의 수는 정사각형 문자열입니까?

DP 솔루션을 시도했지만이 제약 조건을 피할 수없는 것 같습니다 : S will have at most 200 lowercase characters (a-z). 내가 아는 바로는

는 길이 n 목록의 모든 서브 시퀀스를 찾는 30

가 체계적으로 확인하기 위해 정말 가능, 말,보다 큰 곧 n로 실현되는 정지하는 O(2^n)입니다 n이 200이면 모든 솔루션? 어떻게 접근합니까?

Answer 1

첫째, 모든 편지 a..z 당신은 S 자신의 인덱스 목록을 가져올 수 :

S: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
      ^  ^^
      r1  l2 r2 

이 (f(r1,l2,r2)이 평방 시퀀스을 수하자 :

`p[x] = {i : S[i] = x}`, where `x = 'a',..,'z'`. 

그런 다음 우리는 DP 시작 정사각형 문자열 인 서브 시퀀스)가 L이고

SS[2L-1] = r2

전반부 r1 정확히 끝나는 즉

SS[L] = l2

1. SS[L-1] = r1
363,210은 후반전 l2 정확히 r2 시작에서 종료한다.

알고리즘은 다음이다 :

가 f[r1,l2,l2] = 1 결국 0

for (l2 in 1..2L-1) 
    for(r1 in 0..l2-1) 
     for (r2 in l2..2L-1) 
      if(f(r1, l2, r2) != 0) 
       for (x in 'a'..'z') 
        for (i,j: r1 < i < l2, r2 < j, S[i] = S[j] = x) // these i,j are found using p[x] quickly 
         f[i, l2, j] += f[r1, l2, r2] 

또, S[r1] = S[l2] 경우, 응답은 f[.,.,.] 배열의 모든 값들의 합은하자.

기본적으로 S unisg l2을 두 부분으로 나눈 다음 공통 부분 시퀀스를 계산합니다.

지금 정확한 시간 복잡도 추정을 제공하기가 어렵습니다. 에 대해서는 분명히 n^4 및 n^4 미만일 수 있습니다.

Answer 2

선형 시간에 프리픽스 길이 배열을 생성 할 수있는 많은 알고리즘 (예 : Z-algorithm)이 있습니다. 그것은 모든 위치에 대해 i 위치에서 시작하여 읽을 수있는 가장 긴 접두사가 무엇인지 알려줍니다 (물론 i = 0 인 경우 longetst 접두어는 n입니다).

처음부터 시작하는 정사각형 문자열이있는 경우이 접두사 길이 배열에 최대 길이가> = k가되도록 위치 k가 있습니다. 따라서 선형 시간으로 그 수를 다시 계산할 수 있습니다.

그런 다음 첫 번째 문자를 제거하고 동일한 작업을 수행하십시오. 총 복잡도는 O (n^2)입니다.