manacher 's Algorithm: 가장 긴 회 문 열 을 찾 는 O (n) 알고리즘

이것 은 시간 복잡 도가 O (n) O (n) 인 효율 적 인 문자열 답장 서브 문자열 의 동적 계획 알고리즘 이다.인터넷 에 글 이 많 습 니 다. 저 는 주로 가장 긴 답장 문자열 인 Manacher 알고리즘 을 참고 합 니 다.
그의 사상 은 다음 과 같다.

알고리즘 설명

code

복잡 도 분석

연습

알고리즘 설명
하나의 문자열, str, (e. g: str = "agga") 에 대해 그의 답장 서브 문자열 은 두 가지 상황 이 있 기 때문에 1 은 문자열 의 자 모 를 중심 으로 하 는 길이 가 홀수 인 문자열 이 고 2 는 간격 을 중심 으로 하 는 길이 가 짝수 인 문자열 입 니 다.따라서 먼저 채 워 넣 기:
str_pad = "\ # a \ # g \ # g \ # a \ #" 이렇게 하면 답장 문자열 은 모두 문자 중심 입 니 다.
R [i] 문자 str [i] s t [i] 를 중심 으로 하 는 가장 긴 회 문 꼬치 의 반지름 을 기록 합 니 다.분명히 (R [i] - 1) 는 원래 의 회 문 꼬치 길이 이다.

옮 겨 다 니 기 i = 1: n i = 1: n 은 모든 R [i] R [i] 를 계산 하고 mr m r 는 현재 옮 겨 다 니 는 문자열 중 답장 문자열 의 가장 오른쪽 점 이 며, 동시에 zx z x 는 현재 가장 오른쪽 점 의 답장 문자열 의 중심 이다. 즉 (zx - mr, zx + mr) (z x - m r, z x + m r) 은 반드시 답장 문자열 이다.그러면 현재 계 산 된 점 i 는 두 가지 상황 이 있다. a. zx < i < mr z x < i < m r, 이때 zx x 에 관 한 대칭 점 은 j = 2zx - i j = 2z x - i 이다.대칭 성: R [i] ≥ min {R [j], mr - i} R [i] ≥ m i n {R [j], m r - i} 따라서 우 리 는 이때 의 R [i] R [i] 에서 뒤로 계속 일치 할 수 있다.
code
위의 묘 사 는 약간 간단 하 므 로, 문장의 첫머리 문장 중의 그림 과 결합 하여 이해 하 는 것 을 건의 합 니 다.

char str[MAXN],pp[MAXN*2];
int R[MAXN*2]; //      
int n,len;
void manacher(){
    // preprocess
    n = strlen(str+1);
    len=1;
    char pad = '#';
    pp[0] = '$';
    for(int i=1 ; i <= n ; ++i){
        pp[len++] = pad;
        pp[len++] = str[i];
    }
    pp[len++] = pad;
    ms(R,0);
    int mr=0,zx =0;//mr           
    for(int i=1 ; i i? min(R[2*zx -i],mr -i) : 1;
        while (pp[i+R[i]]==pp[i-R[i]])++R[i];
        if(i+R[i]> mr){
            mr = i+R[i];
            zx = i;
        }
    }
}

복잡 도 분석
mr 이동 만 효과적으로 일치 하기 때문에 mr m r 이동 횟수 는 시간 복잡 도 O (n) O (n)
연습 하 다.
유전자 합성 문제 풀이

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

manacher 's Algorithm: 가장 긴 회 문 열 을 찾 는 O (n) 알고리즘

이것 은 시간 복잡 도가 O (n) O (n) 인 효율 적 인 문자열 답장 서브 문자열 의 동적 계획 알고리즘 이다.인터넷 에 글 이 많 습 니 다. g: str = "agga") 에 대해 그의 답장 서브 문자열 은...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

manacher 's Algorithm: 가장 긴 회 문 열 을 찾 는 O (n) 알고리즘

좋은 웹페이지 즐겨찾기