회 문 트 리 (Palindrome Tree) / 회 문 자동 기기 (Palindrome Automation) 학습 수기

간단 한 소개
리 턴 트 리 (리 턴 자동 동기) 는 리 턴 문자열 문 제 를 해결 하 는 강력 한 데이터 구조 로 Manacher 보다 많은 기능 을 확장 했다.이 데이터 구 조 는 전투 민족 의 신 번 미 하 일 루 빈 치 크 가 2014 년 페 트 로 자 보 츠 크 여름 캠프 에서 제시 한 것 으로 비교적 새롭다.이 데이터 구조 코드 의 양은 사실 매우 적다.
필수 기능
Manacher 는 최소한 하나의 자동 기 를 사용 하 는 것 이 좋 습 니 다.
분석 하 다.
회 문 나 무 는 엄 밀 히 말 하면 두 그루 의 나무 로 구 성 된 숲 에 접미사 체인 (어 울 리 지 않 는 사슬) 을 더 했다.그 중 한 그루 의 나 무 는 길이 가 홀수 인 회 문 열 을 대표 하고, 다른 한 그루 의 나 무 는 길이 가 짝수 인 회 문 열 을 대표 한다.트 리 의 모든 노드 는 다른 노드 와 다른 답장 문자열 을 대표 하기 때문에 모든 점 에 길이 len 과 출현 횟수 cnct 와 같은 값 이 있 습 니 다.접미사 체인 fail 은 이 점 으로 대표 되 는 리 턴 문자열 의 가장 긴 리 턴 접미사 점 (약간 길 고 스스로 단문) 을 연결 합 니 다.처음에 짝수 트 리 의 뿌리 노드 는 빈 문자열 을 대표 하고 길 이 는 0 이 며 접미사 체인 은 홀수 트 리 의 뿌리 노드 에 연결 되 어 있 습 니 다.홀수 나무의 뿌리 노드 는 신 을 비교 하 는데 한 글자 가 삼 켜 진 꼬치 (귀신 이 아 닙 니까???) 를 대표 합 니 다. 길 이 는 - 1 (뒤에 왜 그 랬 는 지 말 합 니 다) 이 고 접미사 체인 은 자신 에 게 연 결 됩 니 다.삽입 작업 과정 에서 현재 삽 입 된 문자열 의 최 장 답장 접미사 suf 를 기록 해 야 합 니 다.원래 문자열 을 s 로 설정 합 니 다. 우리 가 첫 번 째 문 자 를 넣 으 려 고 할 때 우 리 는 suf 라 는 점 에서 시작 하여 뒤로 연결 되 어 있 습 니 다. 한 점 x 에 도달 할 때 까지 s [i - 1 - len [x] = s [i], 즉 이 점 을 대표 하 는 답장 접미사 양쪽 문자 가 같 으 면 새로운 답장 문자열 이 될 수 있 습 니 다. (주의: 우리 가 홀수 나무 뿌리 에 뛰 어 들 때 s [i - 1 - len [x] = s [i - 1 - (- 1) = s [i]이렇게 해서 우 리 는 본질 적 으로 단일 문자 인 답장 문자열 을 넣 었 다.우 리 는 x 점 을 찾 은 후에 x 에 양쪽 문자 가 s [i] 인 아들 노드 가 존재 하 는 지 판단 하고 있 으 면 아들 노드 의 cnct 를 하나 더 합 니 다.그렇지 않 으 면 새 노드, cnct 는 1 입 니 다.그럼 새로 만 든 포인트 의 접미사 체인 은 어떻게 하나 요?우 리 는 fail [x] 에 대해 같은 과정 을 할 수 있다.。
블 로그 메 인 이 너무 게 을 러 서 그림 이 어 울 리 지 않 습 니 다. 코드 와 결합 하여 이해 하 세 요.
나 무 를 다 만 들 고 나 면 우 리 는 모든 답장 꼬치 의 출현 횟수 를 다시 계산 해 야 한다.과정 은 매우 간단 합 니 다. 바로 거꾸로 매 거 진 노드 입 니 다. x 에 매 거 진 것 을 가정 하면 우 리 는 cnct [fail [x] 에 cnct [x] 를 추가 하면 됩 니 다.그리고 나머지 는 문 제 를 결합 해서 마구 잡 이 로 하 는 거 야.
코드 구현
주: 다음 코드 는 문제 [APIO 2014] 에 대응 하 는 문자열 이자 알고리즘 의 출처 이 므 로 여러분 이 해 보 시 는 것 을 추천 합 니 다.

#include 
#include 
#include 

using namespace std;

const int N=300005;
const int C=26;

long long ans;
char str[N];
int n;

struct Palindrome_Tree
{
    int next[N][C],cnt[N],fail[N],len[N];
    int tot,suf;

    int newnode()
    {
        for (int i=0;i0;
        cnt[tot]=0,fail[tot]=0;
        return tot++;
    }

    void init()
    {
        tot=0;
        int p;
        len[p=newnode()]=0;
        p=fail[p]=newnode();
        len[p]=-1;
        fail[p]=p;
        suf=0;
    }

    int getfail(int x,int l)
    {
        while (str[l-1-len[x]]!=str[l])
            x=fail[x];
        return x;
    }

    int insert(int x)
    {
        int c=str[x]-'a';
        int p=getfail(suf,x);
        if (!next[p][c])
        {
            int q=newnode();
            len[q]=len[p]+2;
            fail[q]=next[getfail(fail[p],x)][c];
            next[p][c]=q;
        }
        p=next[p][c];
        cnt[p]++;
        suf=p;
        return suf;
    }

    void calc()
    {
        for (int i=tot-1;i>=0;i--)
        {
            ans=max(ans,1ll*cnt[i]*len[i]);
            cnt[fail[i]]+=cnt[i];
        }
    }
}t;

int main()
{
    freopen("palindrome.in","r",stdin);
    freopen("palindrome.out","w",stdout);
    scanf("%s",str);
    n=strlen(str);
    t.init();
    for (int i=0;iprintf("%lld
",ans);
    fclose(stdin);
    fclose(stdout);
}

복잡 도
일단 정리 가 있어 요.

   n                  n。

증명 이 많 습 니 다. Manacher 알고리즘 과정 을 통 해 증명 할 수 있 고 문자열 의 특성 도 분석 할 수 있 습 니 다. 여기 서 더 이상 토론 하지 않 고 참고 자료 의 마지막 강 의 를 했 습 니 다.그리고 공간의 복잡 도 는 분명히 O (n |Σ|) （ Σ 문자 집합) 이나 O (n) 를 위해 서 는 트 리 를 어떻게 저장 하 느 냐 에 달 려 있 습 니 다. 시간 복잡 도 는 제 가 이렇게 분 석 했 습 니 다. 우 리 는 접미사 체인 의 길 이 를 고려 합 니 다. 가장 많 게 는 n 입 니 다. 매번 삽입 하 는 과정 은 접미사 체인 의 길 이 를 약간 줄 인 후에 1 을 더 하 는 것 과 같 습 니 다. (fail 을 계산 하 는 과정 포함)길 이 는 최대 n 회 를 더 하면 분명히 우 리 는 최대 n 회 만 줄 일 수 있 기 때문에 시간 복잡 도 는 O (n) 이다.
참고 자료
해외 블 로그:http://adilet.org/blog/25-09-14/ Codeforces 의 소개:http://codeforces.com/blog/entry/13959 게 으 르 지 않 은 사람.http://blog.csdn.net/u013368721/article/details/42100363 PDF 의 논문 (원 논문 이 아니 라 저자 Victor Wonder, 상세 하 게 썼 고 UOJ 에 링크 가 있 음)：PalindromicTree.pdf