回文树

数据结构与算法
字数统计: 2.7k字   |   阅读时长≈ 11分钟

回文树的总结

回文树详解

今天我们来学习一个神奇的数据结构：Palindromic Tree。中译过来就是——回文树。

那么这个回文树有何功能？

回文树的功能

假设我们有一个串S，S下标从0开始，则回文树能做到如下几点：

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

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

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

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

回文树的构造过程

那么我们该如何构造回文树？

首先我们定义一些变量。

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表示添加的字符个数。

一开始回文树有两个节点，0表示偶数长度串的根和1表示奇数长度串的根，且len[0] = 0，len[1] = -1，last = 0，S[0] = -1，n = 0，p = 2（添加了节点0、1）。

img
img

假设现在我们有串S = abbaabba。

首先我们添加第一个字符’a’，S[++ n] = ‘a’，然后判断此时S[n - len[last] - 1]是否等于S[n]，即上一个串-1的位置和新添加的位置是否相同，相同则说明构成回文。否则，last = fail[last]。此时last = 0，我们发现S[1 - 0 - 1] != S[1]，所以last = fail[last] = 1，然后我们发现S[1 - (-1) - 1] == S[1]（即自己等于自己，所以我们让len[1]等于-1可以让这一步更加方便）。

令cur等于此时的last（即cur = last = 1），判断此时next[cur][‘a’]是否已经有后继，如果next[cur][‘a’]没有后继，我们就进行如下的步骤：新建节点（节点数p++，且之后p = 3），并让now等于新节点的编号（now = 2），则len[now] = len[cur] + 2（每一个回文串的长度总是在其最长子回文串的基础上在两边加上两个相同的字符构成的，所以是+2，同时体现出我们让len[1] = -1的优势，一个字符自成一个奇回文串时回文串的长度为(-1) + 2 = 1）。然后我们让fail[now] = next[get_fail ( fail[cur] )][‘a’]，即得到fail[now]（此时为fail[2] = 0），其中的get_fail函数就是让找到第一个使得S[n - len[last] - 1] == S[n]的last。然后next[cur][‘a’] = now。

当上面步骤完成后我们让last = next[cur][c]（不管next[cur][‘a’]是否有后继），然后cnt[last] ++。

此时回文树为下图状态：

img
img

现在我们添加第二个字符字符’b’到回文树中：

img
img

继续添加第三个字符’b’到回文树中：

img
img

继续添加第四个字符’a’到回文树中：

img
img

继续添加第五个字符’a’到回文树中：

img
img

继续添加第六个字符’b’到回文树中：

img
img

继续添加第七个字符’b’到回文树中：

img
img

继续添加第八个字符’a’到回文树中：

img
img

到此，串S已经完全插入到回文树中了，现在所有的数据如下：

img

然后我们将节点x在fail指针树中将自己的cnt累加给父亲，从叶子开始倒着加，最后就能得到串S中出现的每一个本质不同回文串的个数。

回文树的复杂度

构造回文树需要的空间复杂度为O（N字符集大小），时间复杂度为O（Nlog（字符集大小）），这个时间复杂度比较神奇。如果空间需求太大，可以改成邻接表的形式存储，不过相应的要牺牲一些时间。

模板

1
复制#include <iostream>
2
#include<bits/stdc++.h>
3
using namespace std;
4
const int MAXN = 210005 ;
5
const int N = 26 ;
6
7
struct Palindromic_Tree {
8
    int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
9
    int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
10
    long long cnt[MAXN] ;
11
    //cnt[i]表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
12
    int num[MAXN] ; //num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数
13
    int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
14
    int S[MAXN] ;//存放添加的字符
15
    int last ;//指向上一个字符所在的节点，方便下一次add
16
    int n ;//字符数组指针
17
    int p ;//节点指针
18
19
    int newnode ( int l ) {//新建节点
20
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
21
        cnt[p] = 0 ;
22
        num[p] = 0 ;
23
        len[p] = l ;
24
        return p ++ ;
25
    }
26
27
    void init () {//初始化
28
        p = 0 ;
29
        newnode (0) ;
30
        newnode (-1) ;
31
        last = 0 ;
32
        n = 0 ;
33
        S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
34
        fail[0] = 1 ;
35
    }
36
37
    int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
38
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
39
        return x ;
40
    }
41
42
    void add ( int c ) {
43
        c -= 'a' ;
44
        S[++ n] = c ;
45
    //  cout<<n<<" "<<(char)(S[n]+'a')<<endl;
46
        int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
47
        if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
48
            int now = newnode ( len[cur] + 2 ) ;//新建节点
49
            fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
50
            next[cur][c] = now ;
51
            num[now] = num[fail[now]] + 1 ;
52
        }
53
        last = next[cur][c] ;
54
        cnt[last] ++ ;
55
    }
56
57
    void count () {
58
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
59
        //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
60
    }
61
    void print()
62
    {
63
        //S[i]表示第i次添加的字符（一开始设S[0] = -1（可以是任意一个在串S中不会出现的字符））
64
        for(int i=1;i<=p-2;i++)
65
        {
66
            printf("%c ",S[i]+'a');
67
        }
68
        printf("\n");
69
        for(int i=2;i<p;i++)
70
        {
71
            printf("%d ",cnt[i]);
72
        }
73
        printf("\n");
74
        for(int i=2;i<p;i++)
75
        {
76
            printf("%d ",num[i]);
77
        }
78
        printf("\n");
79
    }
80
} ;
81
Palindromic_Tree a1,b1;
82
long long ans;
83
char a[201312],b[223123];
84
void dfs(int x,int y)
85
{
86
87
    for(int i=0;i<N;i++)
88
    {
89
        int x1 =a1.next[x][i];
90
        int y1 =b1.next[y][i];
91
92
        if(x1&&y1)
93
        {
94
            ans+=(long long)(a1.cnt[x1]*b1.cnt[y1]);
95
            cout<<a1.cnt[x1]<<" "<<b1.cnt[y1]<<endl;
96
            dfs(x1,y1);
97
        }
98
    }
99
}
100
int main()
101
{
102
103
    int T;
104
    cin>>T;
105
    int yy =0;
106
    while(T--)
107
    {
108
        scanf("%s%s",a,b);
109
        yy++;
110
        printf("Case #%d: ",yy);
111
        int len1 =strlen(a);
112
        int len2 =strlen(b);
113
         a1.init();
114
         b1.init();
115
        for(int i=0;i<len1;i++)
116
        {
117
            a1.add(a[i]);
118
        }
119
        for(int i=0;i<len2;i++)
120
        {
121
            b1.add(b[i]);
122
        }
123
        a1.count();
124
        b1.count();
125
        a1.print();
126
        cout<<endl;
127
        b1.print();
128
        ans =0 ;
129
        dfs(0,0);
130
        cout<<endl;
131
        cout<<endl;
132
        dfs(1,1);
133
        cout<<ans<<endl;
134
135
    }
136
    return 0;
137
}

题集

题集链接

“https://cn.vjudge.net/contest/283852#overview"

简易题解

A UVALive 7041 【裸】
题意：求两个串的公共回文串的个数。

B HDU 3068【裸】
题意：求最长回文串的长度

C HDU 3948 【裸】
题意：求出本质不同的回文串个数。

D HYSBZ 2565
题意：求最长双回文子串的长度
正着跑一遍，反着跑一遍即可。

E URAL 1960
题意：求字符串的所有前缀 本质不同的回文串个数。
在添加字符的过程中直接输出即可。

F HYSBZ 3676
题意：我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

G HDU 5658
题意：给定一个串，询问l到r右多少本质不同的回文串。

H HDU 5157

题意 ：给定一个字符串str，求str的不相交的回文子串的对数。
回文树num数组的运用。

I HYSBZ 2160
题意：给一个字符串，求最长的k个回文子串（此处回文子串长度必须为奇数）
长度的乘积。字符串长度≤1000000，即要将回文串按照长度从大到小选择k个出来,并求出长度乘积。

J HDU - 5785
题意：给你一个串，定义了一个权值，每个权值是两个回文串拼起来的左右坐标乘积。求所有权值的和。

注意细节，不然会爆空间

K CodeForces 17E
题意：求一个字符串中相交回文串的对数。

L HDU 5421（回文树扩展——可左右添加字符的回文树）
题意：有n种操作，开始给你一个空串，给你4种操作。
1 c 在字符串的首部添加字符c
2 c 在字符串的尾部添加字符c
3 询问字符中的本质不同的回文串的个数
4 询问字符串中回文串的个数

参考博客

https://blog.csdn.net/u013368721/article/details/42100363
http://axuhongbo.top/tree/

  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信