2019 우 커 다 교 6 차 전 C. Palindrome Mouse (리 턴 트 리)

꼬치 를 주 고 이 꼬치 에 있 는 모든 본질 이 다른 답문 서브 꼬치 가 얼마나 많은 지 물 어보 세 요. 한 꼬치 를 만족 시 키 는 것 은 다른 하위 꼬치 입 니 다.
이 문 제 는 현장에서 보 낸 사람 이 매우 적 습 니 다. 문제 풀이 도 복잡 합 니 다. 제 가 아직 이해 하지 못 한 log 를 가 진 방법 을 주 었 습 니 다. 사실은 회 문 수 를 알 면 너무 보고 싶 습 니 다. 우 리 는 현장에서 O (n) 방법 (소 손님 이 72ms 를 달 렸 습 니 다) 을 썼 습 니 다.회 문 나 무 는 새로운 것 이 라 고 할 수 있 습 니 다. 아직 망 가지 지 않 았 습 니 다. 제 가 예전 에 칠 한 회 문 트 리 세트 문 제 는 모두 판자 문제 라 고 할 수 있 습 니 다. 최근 에 여러 학교 에서 몇 개의 회 문 트 리 가 유연 하 게 운용 하 는 범주 에 들 어 갔 습 니 다. 출제 자 는 이 알고리즘 을 망 가 뜨리 려 고 준 비 했 습 니 다. 앞으로 이것 은 모두 기본 적 인 체조 입 니 다.
본질 이 다 르 기 때문에 답문 의 자동 동 기 를 생각 한 다음 에 답문 나무 에 정리 하기 시 작 했 습 니 다. 어떤 두 노드 가 나타 내 는 답문 꼬치 는 하위 꼬치 관계 가 있 습 니까?
먼저 next 쪽 입 니 다. 분명 한 것 은 next 체인 에 기 근 우 근 을 제외 하고 모든 아버 지 는 아들 의 꼬치 입 니 다.그 다음은 fail 변 이 고 분명 하 다. fail 체인 에 아버 지 는 아들 의 접미사 이기 때문에 기 근 우 근 을 제외 한 모든 아버 지 는 아들 의 꼬치 이다.
자, 이 문 제 는 곧 끝난다.각 노드 에 대한 답 은 next 체인 에서 뿌리 를 제외 한 아버지 개수 + fail 체인 에서 뿌리 를 제외 한 아버지 개수 입 니 다.그러나 이것 만 문제 가 존재 합 니 다. next 체인 과 fail 체인 은 가끔 교차 가 존재 하기 때 문 입 니 다. 즉, 하나의 답장 문자열 은 다른 문자열 의 접미사 이자 그 문자열 사이 에 나타 납 니 다. 예 를 들 어 사례 의 aaaa, next 체인 의 aa 와 fail 체인 의 aa 는 같은 노드 입 니 다.
그래서 어떻게 든 무 거 운 곳 으로 가 야 한다.dfs 와 각 노드 에 fail 트 리 를 통계 할 때 vis 표 시 를 합 니 다 (현재 노드 도 표시 해 야 합 니 다. next 체인 과 fail 체인 이 무 거울 때 여기까지 뛰 어 올 수 있 습 니 다). 만약 에 다음 에 뛸 때 vis 를 발견 하면 멈 출 수 있 습 니 다. 그러면 교차 하지 않 고 fail 트 리 의 중복 점프 가 가 져 오 는 복잡 도 를 간단하게 보장 할 수 있 습 니 다.
마지막 으로 뛰 어 나 온 것 에 대해 간단 한 dp 를 만 듭 니 다. 현재 노드 공헌 = 아버지 공헌 + fail 체인 공헌 + 1.
ac 코드:

#include 

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int _, kase = 1;
char s[maxn];
ll ans = 0;

struct Pam {
    int next[maxn][26];
    int fail[maxn];
    int len[maxn];//             
    int S[maxn];
    int dp[maxn];
    bool vis[maxn];
    int last, n, p;


    int newNode(int l) {
        memset(next[p], 0, sizeof(next[p]));
        len[p] = l;
        dp[p] = 0;
        return p++;
    }

    void init() {
        ans = 0;
        n = last = p = 0;
        newNode(0);
        newNode(-1);
        S[n] = -1;
        fail[0] = 1;
    }

    int getFail(int x) {
        while (S[n - len[x] - 1] != S[n]) {
            x = fail[x];
        }
        return x;
    }

    void add(int c) {
        S[++n] = c;
        int cur = getFail(last);
        if (!next[cur][c]) {
            int now = newNode(len[cur] + 2);
            fail[now] = next[getFail(fail[cur])][c];
            next[cur][c] = now;
        }
        last = next[cur][c];
    }

    int jump(int x) {
        int cnt = 0;
        vis[x] = 1;
        while (fail[x] != 0 && fail[x] != 1 && !vis[fail[x]]) {
            x = fail[x];
            vis[x] = 1, ++cnt;
        }
        return cnt;
    }

    void clearJump(int x, int cnt) {
        vis[x] = 0;
        while (cnt--) {
            x = fail[x];
            vis[x] = 0;
        }
    }

    void dfs(int x, int fa) {
        int jp = jump(x);
        dp[x] = jp;
        if (x != 1 && x != 0 && fa != 0 && fa != 1) {
            dp[x] = dp[fa] + jp + 1;
        }
        ans += dp[x];
        for (int i = 0; i < 26; ++i) {
            if (next[x][i]) {
                dfs(next[x][i], x);
            }
        }
        clearJump(x, jp);
    }

    void build() {
        init();
        for (int i = 1; s[i]; i++) {
            add(s[i] - 'a');
        }
    }

} pam;


int main() {
    scanf("%d", &_);
    while (_--) {
        scanf("%s", s + 1);
        pam.build();
        printf("Case #%d: ", kase++);
        pam.dfs(1, 1);
//        printf("%lld
", ans);
        pam.dfs(0, 0);
        printf("%lld
", ans);
    }
    return 0;
}