回文树

应用场景

1.求串S前缀font>0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）

2.求串S内每一个本质不同回文串出现的次数

3.求串S内回文串的个数（其实就是1和2结合起来）

4.求以下标i结尾的回文串的个数

参考资料:

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

17年国家集训队论文《回文树及其应用》

定义变量

1.len 表示编号为i的节点表示的回文串的长度（一个节点表示一个回文串）

2.next 表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（和字典树类似）。

3.fail 表示节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串（和AC自动机类似）。

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

5.num 表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。

6.last 指向新添加一个字母后所形成的最长回文串表示的节点。

7.S 表示第i次添加的字符（一开始设S[0] = -1（可以是任意一个在串S中不会出现的字符））。

8.p 表示添加的节点个数。

9.n 表示添加的字符个数。

由于代码风格不同

本文全部代码均由上文博客地址中的代码改写而成

缺点: 速度慢

例如: UESTC-1999

上边的为我的模板的提交结果 TLE
下边的为改为原博主的模板后的提交结果,1421ms飘过
时限1500ms

Status	Length	Submitted	RemoteRunId
Time Limit Exceeded on test 59	3139	2018-09-03 01:39:57	432786

Status	Time	Memory	Length	Submitted	RemoteRunId
Accepted	1421ms	1524kB	2827	2018-09-03 01:51:36	432792

预定义

 1 const int MAXN = 1e5+10;
 2 const int N = 26;
 3 char s[MAXN];
 4 struct node
 5 {
 6     int next[N];   // next指针,next指针和字典树类似,指向的串为
 7                    // 当前穿两端加上同一个字符构成
 8     int fail;      // fail指针,失配后跳转到fail指针指向的节点
 9     int cnt;       // 表示节点i的本质不同的串的个数
10                    // 建树时求出的不是完全的，最后Count()函数跑一遍以后才是正确的
11     int num;       // 表示以节点i表示的最长回文串的最右端点为回文串结尾的回文个数
12     int len;       // 表示以当前节点表示的最长回文串长度（一个节点表示一个回文串）
13     int S;         // 存放添加的字符
14 }pam[MAXN];
15 int last;   // 指向新添加一个字母后所形成的最长回文串表示的节点
16 int n;      // 表示添加的字符个数
17 int p;      // 表示添加的节点个数

新建节点

int newnode(int x)
{
    for(int i = 0;i < N;i++)
        pam[p].next[i] = 0;
    pam[p].cnt = 0;
    pam[p].num = 0;
    pam[p].len = x;
    return p++;
}

初始化

 1 void Init()
 2 {
 3     p = 0;
 4     newnode(0);
 5     newnode(-1);
 6     last = 0;
 7     n = 0;
 8     pam[n].S = -1;   // 开头存放一个字符集中没有的字符,减少特判
 9     pam[0].fail = 1;
10 }

构造失配指针

1 int get_fail(int x)
2 {
3     while(pam[n-pam[x].len-1].S != pam[n].S)
4         x = pam[x].fail;
5     return x;
6 }

添加字母

void Add(int c)
{
    c -= 'a';
    pam[++n].S = c;
    int cur = get_fail(last);   // 通过上一个回文串找这个回文串的匹配位置
    if(!pam[cur].next[c])       // 如果这个回文串没有出现过，说明出现了
                                // 一个新的本子不同的回文串
    {
        int now = newnode(pam[cur].len+2);   // 新建节点
        pam[now].fail = pam[get_fail(pam[cur].fail)].next[c];   
        // 和AC自动机一样建立fil指针,以便失败后回跳
        pam[cur].next[c] = now;
        pam[now].num = pam[pam[now].fail].num+1;
    }
    last = pam[cur].next[c];
    pam[last].cnt++;
}

Count函数

1 void Count()
2 {
3     for(int i = p-1;i >= 0;--i)
4     {
5         pam[pam[i].fail].cnt += pam[i].cnt;
6         // 父亲累加儿子才cnt,因为如果fail[v] = u , 则u一定是v的子回文串
7     }
8 }

主函数

 1 int main()
 2 {
 3     scanf("%s",s);   // 读入字符串
 4     int len = strlen(s);
 5     Init();          // 初始化
 6     for(int i = 0;i < len;i++)
 7         Add(s[i]);
 8     Count();         // Count()函数跑一遍cnt的值以后才是正确的
 9     printf("balabalabala~~~");
10     return 0;
11 }

原文模板

速度比我改写的要快

 1 const int MAXN = 100005 ;
 2 const int N = 26 ;
 3 struct Palindromic_Tree {
 4     int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
 5     int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
 6     int cnt[MAXN] ;
 7     int num[MAXN] ;
 8     int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
 9     int S[MAXN] ;//存放添加的字符
10     int last ;//指向上一个字符所在的节点，方便下一次add
11     int n ;//字符数组指针
12     int p ;//节点指针
13  
14     int newnode ( int l ) {//新建节点
15         for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
16         cnt[p] = 0 ;
17         num[p] = 0 ;
18         len[p] = l ;
19         return p ++ ;
20     }
21  
22     void init () {//初始化
23         p = 0 ;
24         newnode (  0 ) ;
25         newnode ( -1 ) ;
26         last = 0 ;
27         n = 0 ;
28         S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
29         fail[0] = 1 ;
30     }
31  
32     int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
33         while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
34         return x ;
35     }
36  
37     void add ( int c ) {
38         c -= 'a' ;
39         S[++ n] = c ;
40         int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
41         if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
42             int now = newnode ( len[cur] + 2 ) ;//新建节点
43             fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
44             next[cur][c] = now ;
45             num[now] = num[fail[now]] + 1 ;
46         }
47         last = next[cur][c] ;
48         cnt[last] ++ ;
49     }
50  
51     void count () {
52         for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
53         //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
54     }
55 } ;

View Code

练手习题

BZOJ3676

RunID Problem Result Memory Time Submit_Time

2937794 3676 Accepted 38036 kb 1252 ms 2018-09-03 00:59:48

UESTC-1999

Status Time Memory Length Submitted RemoteRunId

Accepted 1421ms 1524kB 2827 2018-09-03 01:51:36 432792