回文树

说明

原文链接:Palindromic Tree——回文树【处理一类回文串问题的强力工具】

  1. len[i]表示编号为i的节点表示的回文串的长度(一个节点表示一个回文串)
  2. next[i][c]表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号(和字典树类似)。
  3. fail[i]表示节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串(和AC自动机类似)。
  4. cnt[i]

    表示节点i表示的本质不同的串的个数(建树时求出的不是完全的,最后count()函数跑一遍以后才是正确的)

    看了半天没看懂有什么卵用,等我用到了再回来补
  5. num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
  6. last指向新添加一个字母后所形成的最长回文串表示的节点。
  7. S[i]表示第i次添加的字符(一开始设S[0] = -1(可以是任意一个在串S中不会出现的字符))。
  8. p下一个被插入的位置下标
  9. n已插入的字符数量

使用方法

  • Palindromic_Tree p;
  • p.init();初始化
  • int tmp = p.add(str[i]); 依次加入字符串中的每个字符,返回的tmp为以当前字符结尾的回文串数量
  • 全部插入之后,以插入的第i个字符结尾的回文串的个数为num[i+1],最大长度为len[i+1],其中i的下标在[1, Len]区间

Tips

  • 注意maxLenSIGMA_SIZE
  • scanf("%s", str+1); 下标从1开始

模版

const int maxLen = 100005 ;
const int SIGMA_SIZE = 26 ;
struct Palindromic_Tree {
    int next[maxLen][SIGMA_SIZE] ;//next指针,next指针和字典树类似,指向的串为当前串两端加上同一个字符构成
    int fail[maxLen] ;//fail指针,失配后跳转到fail指针指向的节点
    int cnt[maxLen] ;
    int num[maxLen] ;//以该节点结束的回文串的数量
    int len[maxLen] ;//len[i]表示 以i结尾的最大回文串的长度
    int S[maxLen] ;//存放添加的字符
    int last ;//指向上一个字符所在的节点,方便下一次add
    int n ;//已插入的字符数量
    int p ;//下一个被插入的位置下标

    int newnode ( int l ) {//新建节点
        for ( int i = 0 ; i < SIGMA_SIZE ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init () {//初始化
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;//开头放一个字符集中没有的字符,减少特判
        fail[0] = 1 ;
    }

    int get_fail ( int x ) {//和KMP一样,失配后找一个尽量最长的
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    int add ( int c ) { //返回以当前字符结尾的回文串个数
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
        if ( !next[cur][c] ) {//如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串
            int now = newnode ( len[cur] + 2 ) ;//新建节点
            fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针,以便失配后跳转
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
        return num[last];
    }

    void count () {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
        //父亲累加儿子的cnt,因为如果fail[v]=u,则u一定是v的子回文串!
    }
};

results matching ""

    No results matching ""