문자열 상용 알고리즘 요약

1477 단어
1. manacher 알고리즘
말 라 차 알고리즘 은 O (n) 시간 내 에 원본 문자열 을 찾 는 가장 긴 답장 서브 문자열 S 문 제 를 해결 하 는 알고리즘 입 니 다.소박 한 알고리즘 의 경우 모든 S [i] 에 대해 좌우 로 최대 답장 문자열 을 옮 겨 다 녀 야 하기 때문에 시간 복잡 도 는 O (n2) 입 니 다.
참고 블 로그:
https://www.cnblogs.com/czsharecode/p/9705358.html
https://www.cnblogs.com/yangxingsha/p/11722557.html(오류 가 있 습 니 다. "왼쪽 에서 오른쪽으로 배열 P [] 를 계산 합 니 다. Mi 는 이전에 가장 큰 답장 문자열 의 중심 위 치 를 얻 었 고 R 은 가장 큰 답장 문자열 이 도착 할 수 있 는 가장 오른쪽 끝 값 입 니 다.")
//      S        
string Manacher(string s){
    //      
    string t = "$#";
    for(int i=0; i p(t.size() , 0); 
    
    //       mx(             ),id(mx         ),
    //reCenter(           ),reLen(       ) 
    int mx = 0, id = 0, reCenter = 0, reLen = 0;
    
    //  t   
    for(int i=1; i i ? min(mx - i , p[2*id - i]) : 1;
        
        //         i~mx     ,  mx         ,           ,    p[i]++ 
        while(t[i + p[i]] == t[i - p[i]]) p[i]++;
        
        // t[i]         mx mx id    
        if(i+p[i] > mx){
            mx = i+p[i];
            id = i;
        }
        //       
        if(p[i] > reLen){
            reLen = p[i];
            reCenter = i;    
        }
    }
    
    return s.substr((reCenter - reLen) / 2 , reLen - 1)  ;
    
}

2. 문자열 해시
https://www.luogu.com.cn/problem/solution/P3370
https://www.luogu.com.cn/blog/yhzq/solution-p3370
3. 사전 트 리

좋은 웹페이지 즐겨찾기