<span>回文树(回文自动机PAM)小结</span>
边写边更新，大概会把回文树总结在一个博客里吧...
回文树的功能
假设我们有一个串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表示添加的字符个数。
板子（来源：poursoul ）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 100005 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pt;
例题
1. ural1960. Palindromes and Super Abilities
题意
给出一个字符串，输出前 i 个字符中有多少个回文串。
题解
每次加入新的字符后输出 p-2 即可（减去两棵树的根节点）
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 100005 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//len[i]表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ; 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 next[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = next[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pt; 64 65 char str[MAXN]; 66 ll ans=0; 67 68 int main() 69 { 70 scanf("%s",str); 71 int len=strlen(str); 72 pt.init(); 73 for(int i=0;i<len;i++) pt.add(str[i]),printf("%d ",pt.p-2); 74 return 0; 75 }
2. 2014-2015 ACM-ICPC, Asia Xian G The Problem to Slow Down You
题意
给定两个字符串A和B，问A中的每个回文串在B中一共出现了多少次
题解
对A和B分别建回文树，然后对回文树的两棵奇偶树分别跑一下dfs就好了
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 200005 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pa,pb; 64 65 char str1[MAXN]; 66 char str2[MAXN]; 67 ll ans=0; 68 69 void dfs(int a,int b) 70 { 71 for(int i=0;i<N;i++){ 72 if(pa.nt[a][i]&&pb.nt[b][i]){ 73 ans+=pa.cnt[pa.nt[a][i]]*1ll*pb.cnt[pb.nt[b][i]]; 74 dfs(pa.nt[a][i],pb.nt[b][i]); 75 } 76 } 77 } 78 79 int main() 80 { 81 int t; 82 scanf("%d",&t); 83 int tt=0; 84 while(t--){ 85 scanf("%s%s",str1,str2); 86 int len1=strlen(str1); 87 int len2=strlen(str2); 88 pa.init(); 89 pb.init(); 90 for(int i=0;i<len1;i++) pa.add(str1[i]); 91 pa.count(); 92 for(int i=0;i<len2;i++) pb.add(str2[i]); 93 pb.count(); 94 ans=0; 95 dfs(0,0); 96 dfs(1,1); 97 printf("Case #%d: ",++tt); 98 printf("%lld\n",ans); 99 } 100 return 0; 101 }
题意
给出一棵树，每棵树给出该节点的元素和其父亲编号，求出这棵树所有回文串的长度*出现的次数。
题解
用邻接表表示这棵树，把回文树中的last变成last数组按深度存储last的值，get_fail部分将last变成last[deep−1]去查找这个回文串的匹配位置。用sum[x]记录结点x的贡献，插入的x如果是新结点，那么sum[now]的值就是sum[fail[now]]+len[now]，失配部分的贡献加上新产生的串的长度。按邻接表dfs插入每个元素，加入回文树后答案加上当前位置的贡献。
这个题有个提示很重要，没看到找了一早上爆栈的原因....如果爆栈了，记得加上这句
代码
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define max(a,b) ((a)>(b)?(a):(b)) 6 #define ll long long 7 using namespace std; 8 9 const int MAXN = 2001000 ; 10 const int N = 30 ; 11 ll ans=0; 12 13 struct Edge{ 14 int to,nt; 15 }edge[MAXN]; 16 17 int head[MAXN],tot; 18 19 void addedge(int u,int v) 20 { 21 edge[tot].to=v; 22 edge[tot].nt=head[u]; 23 head[u]=tot++; 24 } 25 26 struct Palindromic_Tree { 27 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 28 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 29 int len[MAXN] ;//表示节点i表示的回文串的长度 30 int S[MAXN] ;//存放添加的字符 31 int last[MAXN] ;//指向上一个字符所在的节点，方便下一次add 32 ll sum[MAXN]; 33 int n ;//字符数组指针 34 int p ;//节点指针 35 36 int newnode ( int l ) {//新建节点 37 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 38 len[p] = l ; 39 return p ++ ; 40 } 41 42 void init () {//初始化 43 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 44 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 45 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 46 last[0] = 0 ; 47 n = 0 ; 48 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 49 fail[0] = 1 ; 50 } 51 52 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 53 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 54 return x ; 55 } 56 57 void add ( int c , int x ) { 58 c -= 'a' ; 59 n = x ; 60 S[n] = c ; 61 int cur = get_fail ( last[n-1] ) ;//通过上一个回文串找这个回文串的匹配位置 62 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 63 int now = newnode ( len[cur] + 2 ) ;//新建节点 64 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 65 nt[cur][c] = now ; 66 sum[now]=sum[fail[now]]+len[now]; 67 } 68 last[n] = nt[cur][c] ; 69 ans+=sum[last[n]]; 70 } 71 }pt; 72 73 char s[MAXN]; 74 75 void dfs(int u,int x) 76 { 77 for(int i=head[u];~i;i=edge[i].nt){ 78 int v=edge[i].to; 79 pt.add(s[v],x); 80 dfs(v,x+1); 81 } 82 } 83 84 int main() 85 { 86 int t; 87 scanf("%d",&t); 88 while(t--){ 89 tot=0; 90 memset(head,-1,sizeof(head)); 91 pt.init(); 92 int n; 93 scanf("%d",&n); 94 for(int i=1;i<=n;i++){ 95 char ch[10]; 96 int x; 97 scanf("%s%d",ch,&x); 98 s[i]=ch[0]; 99 addedge(x,i); 100 } 101 ans=0; 102 dfs(0,1); 103 printf("%lld\n",ans); 104 } 105 return 0; 106 }
4. Skr
题意
给定一个字符串，求每个回文串的数值之和对mod求余，mod=1e9+7;
题解
一开始想的是每次加入字符 s[x] (从1开始)形成的新的回文串len[now]是它的长度，所以这个回文串的数值就是从x-len[now]到x-1，那么只要遍历算出这个串的数值就好了，然后就愉快的 t 了。
那么就要优化他，空间也得优化，不然很容易爆，因为是数字0~9，所以next数组第二维只要开10就好了，这样就不会爆内存了。
对于时间优化，可以用a数组存s的前缀数值，b数组存pow(10，i )，那么对于x-len[now]到x-1这一段的值就是a[x]-a[x-len[now]]*b[len[now]]（记得取模^_^），类似于哈希的做法。这个地方一开始写成了b[x-len[now]]（我真是憨憨），因为这一段的长度是len[now]，他们之前的差的倍数就是pow(10，len[now]）倍。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 2e6+10 ; 9 const int N = 10 ; 10 const ll mod = 1e9+7 ; 11 char str[MAXN]; 12 ll ans=0; 13 ll a[MAXN],b[MAXN]; 14 15 struct Palindromic_Tree { 16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 18 int len[MAXN] ;//表示节点i表示的回文串的长度 19 int S[MAXN] ;//存放添加的字符 20 int last ;//指向上一个字符所在的节点，方便下一次add 21 int n ;//字符数组指针 22 int p ;//节点指针 23 24 int newnode ( int l ) {//新建节点 25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ,int x ) { 46 c -= '0' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 ans+=((a[x]-a[x-len[now]]*b[len[now]]%mod)%mod+mod)%mod; 54 ans%=mod; 55 } 56 last = nt[cur][c] ; 57 } 58 59 }pt; 60 61 int main() 62 { 63 scanf("%s",str); 64 int len=strlen(str); 65 pt.init(); 66 b[0]=1; 67 for(ll i=1;i<=len;i++) { 68 a[i]=a[i-1]*10+str[i-1]-'0'; 69 a[i]%=mod; 70 b[i]=b[i-1]*10%mod; 71 } 72 for(int i=0;i<len;i++) pt.add(str[i],i+1); 73 printf("%lld\n",ans); 74 return 0; 75 }
题意
给定一个字符串，求每个回文串中不同的字母的个数和。
题解
先建一棵回文树，然后奇偶树分别从根节点开始dfs，用vis数组标记字符是否出现过，遇到没出现过的字符，个数 y 就+1。对于每个结点 x 更新答案ans，也就是ans+=y*cnt[next[x][i]]。根据前边的变量的含义：4.cnt[i]表示节点 i 表示的本质不同的串的个数。也就是不同字符的个数*以结点 x 表示的不同的串的个数。然后继续往下找下一个结点。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 3e5+10 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pt; 64 65 char str[MAXN]; 66 ll ans=0; 67 bool vis[N]; 68 69 void dfs(int x,int y) 70 { 71 for(int i=0;i<N;i++){ 72 if(pt.nt[x][i]){ 73 if(!vis[i]){ 74 vis[i]=1; 75 y++; 76 ans+=y*pt.cnt[pt.nt[x][i]]; 77 dfs(pt.nt[x][i],y); 78 vis[i]=0; 79 y--; 80 } 81 else{ 82 ans+=y*pt.cnt[pt.nt[x][i]]; 83 dfs(pt.nt[x][i],y); 84 } 85 } 86 } 87 } 88 89 int main() 90 { 91 scanf("%s",str); 92 int len=strlen(str); 93 pt.init(); 94 for(int i=0;i<len;i++) pt.add(str[i]); 95 pt.count(); 96 dfs(0,0); 97 memset(vis,0,sizeof(vis)); 98 dfs(1,0); 99 printf("%lld\n",ans); 100 return 0; 101 }
题意
对于一个给定的字符串，他是加密的，要求解密后的字符串的以每个位置为结尾的回文子串个数。若第 i (i≥1) 个位置的答案是 k，第 i+1 个字符读入时的ASCII 码为 c，则第 i+1 个字符实际的 ASCII 码为 (c−97+k)mod26+97。这个题有毒，题意看了3遍都是错的，让我样例都写不出来。他的k是以上一个字符为结尾的回文串的个数，而不是上一个字符。
题解
就是板子题，每次输出上边含义中的（5.num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。）num[last]，并且更新k为num[last]，因为last为新加入回文树的元素的编号。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 5e5+10 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pt; 64 65 char str[MAXN]; 66 ll ans=0; 67 68 int main() 69 { 70 scanf("%s",str); 71 int len=strlen(str); 72 int k=0; 73 pt.init(); 74 for(int i=0;i<len;i++) { 75 str[i]=(str[i]+k-97)%26+97; 76 pt.add(str[i]); 77 printf("%d ",pt.num[pt.last]); 78 k=pt.num[pt.last]; 79 } 80 return 0; 81 }
7. P5555 秩序魔咒
题意
给定两个字符串，求最长的，不同的，且在两个字符串中都出现了的回文串长度和个数。
题解
和第 2 题有点类似，对A和B分别建回文树，然后对回文树的两棵奇偶树分别跑一下dfs，用len[now]更新最长长度，如果出现长度一样的更新答案+1。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 3e5+10 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pa,pb; 64 65 char s[MAXN]; 66 char t[MAXN]; 67 ll ans=0,p=0; 68 69 void dfs(int a,int b) 70 { 71 for(int i=0;i<N;i++){ 72 int x=pa.nt[a][i]; 73 int y=pb.nt[b][i]; 74 if(x&&y){ 75 int q=pa.len[x]; 76 if(q>p) p=q,ans=0; 77 if(q==p){ 78 ans++; 79 } 80 dfs(x,y); 81 } 82 } 83 } 84 85 int main() 86 { 87 int len1,len2; 88 scanf("%d%d",&len1,&len2); 89 scanf("%s%s",s,t); 90 pa.init(); 91 pb.init(); 92 for(int i=0;i<len1;i++) pa.add(s[i]); 93 for(int i=0;i<len2;i++) pb.add(t[i]); 94 pa.count(); 95 pb.count(); 96 dfs(0,0); 97 dfs(1,1); 98 printf("%lld %lld\n",p,ans); 99 return 0; 100 }
题意
给定一个字符串，求字符串中回文串的长度*出现次数最大值。
题解
建一棵回文树，遍历每个结点，用 cnt[i]*len[i] 更新ans的最大值。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 using namespace std; 7 8 const int MAXN = 100005 ; 9 const int N = 26 ; 10 11 struct Palindromic_Tree { 12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。 16 int len[MAXN] ;//表示节点i表示的回文串的长度 17 int S[MAXN] ;//存放添加的字符 18 int last ;//指向上一个字符所在的节点，方便下一次add 19 int n ;//字符数组指针 20 int p ;//节点指针 21 22 int newnode ( int l ) {//新建节点 23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 24 cnt[p] = 0 ; 25 num[p] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 num[now] = num[fail[now]] + 1 ; 54 } 55 last = nt[cur][c] ; 56 cnt[last] ++ ; 57 } 58 59 void count () { 60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; 61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ 62 } 63 }pt; 64 65 char str[MAXN]; 66 ll ans=0; 67 68 int main() 69 { 70 scanf("%s",str); 71 int len=strlen(str); 72 pt.init(); 73 for(int i=0;i<len;i++) pt.add(str[i]); 74 pt.count(); 75 for(int i=2;i<pt.p;i++) ans=max(ans,1ll*pt.cnt[i]*pt.len[i]); 76 printf("%lld\n",ans); 77 return 0; 78 }
题意
给定一个字符串，找出最长的回文串，长度是4的倍数，且回文串的前半部分和后半部分分别是个回文串。
题解
本来以为是两个连着的相同的回文串，结果发现连起来的串也得是回文串...（我可真是读题bug姬
hash的做法：
类似于第4题str，加入元素是判断如果当前这个回文串的长度可以被4整除，那么就可以用hash比较前半段和后半段是否相等，相等的话更新答案。
利用fail数组：
构造一个trans数组，记录小于等于当前节点长度一半的最长回文后缀。每次新建立一个节点的时候，如果他表示的回文串长度小于等于2，那么trans[now]=fail[now]，否则从 trans[父亲] 开始走fail，直到某一个节点所表示的回文串的两侧都能扩展这个字符并且拓展后的长度小于等于他表示的回文串的一半。最后再判断一下当前回文串的长度是否是4的倍数并且 trans[now] 表示的回文串的长度是当前回文串的一半，并更新答案。
代码
hash：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 #define ull unsigned long long 7 using namespace std; 8 9 const int MAXN = 5e5+10 ; 10 const int N = 26 ; 11 char str[MAXN]; 12 ll ans=0; 13 ull a[MAXN],b[MAXN]; 14 const ull base = 131; 15 16 struct Palindromic_Tree { 17 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 18 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 19 int len[MAXN] ;//表示节点i表示的回文串的长度 20 int S[MAXN] ;//存放添加的字符 21 int last ;//指向上一个字符所在的节点，方便下一次add 22 int n ;//字符数组指针 23 int p ;//节点指针 24 25 int newnode ( int l ) {//新建节点 26 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 27 len[p] = l ; 28 return p ++ ; 29 } 30 31 void init () {//初始化 32 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 33 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 34 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 35 last = 0 ; 36 n = 0 ; 37 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 38 fail[0] = 1 ; 39 } 40 41 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 42 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 43 return x ; 44 } 45 46 void add ( int c ,int x ) { 47 c -= '0' ; 48 S[++ n] = c ; 49 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 50 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 51 int now = newnode ( len[cur] + 2 ) ;//新建节点 52 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 53 nt[cur][c] = now ; 54 if(len[now]%4==0){ 55 ull xx=len[now]/2; 56 ull pp=(a[x-xx]-a[x-len[now]])*b[xx]; 57 ull qq=a[x]-a[x-xx]; 58 if(pp==qq) ans=max(ans,len[now]); 59 } 60 } 61 last = nt[cur][c] ; 62 } 63 }pt; 64 65 int main() 66 { 67 int len; 68 scanf("%d",&len); 69 scanf("%s",str); 70 pt.init(); 71 b[0]=1; 72 for(ll i=1;i<=len;i++) { 73 a[i]=a[i-1]*base+str[i-1]; 74 b[i]=b[i-1]*base; 75 } 76 for(int i=0;i<len;i++) pt.add(str[i],i+1); 77 printf("%lld\n",ans); 78 return 0; 79 }
fail：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 #define ull unsigned long long 7 using namespace std; 8 9 const int MAXN = 5e5+10 ; 10 const int N = 26 ; 11 char str[MAXN]; 12 int trans[MAXN]; 13 int ans=0; 14 15 struct Palindromic_Tree { 16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 18 int len[MAXN] ;//表示节点i表示的回文串的长度 19 int S[MAXN] ;//存放添加的字符 20 int last ;//指向上一个字符所在的节点，方便下一次add 21 int n ;//字符数组指针 22 int p ;//节点指针 23 24 int newnode ( int l ) {//新建节点 25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ) { 46 c -= 'a' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 if(len[now]>2){ 54 int x=trans[cur]; 55 while(S[n-len[x]-1]!=S[n]||(len[x]+2)*2>len[now]) x=fail[x]; 56 trans[now]=nt[x][c]; 57 } 58 else trans[now]=fail[now]; 59 if(len[trans[now]]*2==len[now]&&len[now]%4==0) ans=max(ans,len[now]); 60 } 61 last = nt[cur][c] ; 62 } 63 }pt; 64 65 int main() 66 { 67 int len; 68 scanf("%d",&len); 69 scanf("%s",str); 70 pt.init(); 71 for(int i=0;i<len;i++) pt.add(str[i]); 72 printf("%d\n",ans); 73 return 0; 74 }
10. P4762 [CERC2014]Virus synthesis
题意
初始有一个空串，利用下面的操作构造给定串 S。
1、串开头或末尾加一个字符
2、串开头或末尾加一个该串的逆串
求最小化操作数，∣S∣≤1e5 。
题解
肯定能想到套娃找回文串可以执行2更多的，问题是要如何找。这个就可以想上一个题的fail数组的做法那样，构造一个trans数组，记录小于等于当前节点长度一半的最长回文后缀。每次新建立一个节点的时候，如果他表示的回文串长度小于等于2，那么trans[now]=fail[now]，否则从 trans[父亲] 开始走fail，直到某一个节点所表示的回文串的两侧都能扩展这个字符并且拓展后的长度小于等于他表示的回文串的一半。
用dp[i]表示转移到 i 代表的回文串的最少的需要次数。因为要执行操作2，执行后的串肯定是偶数串，所以如果当前回文串的长度为偶数，那么就可以考虑两种情况：
一种是直接从上一个回文串前后都加一个字符，这就相当于是前一半加了字符之后再翻转，相当于步数+1，dp[now]=dp[cur]+1。
另一种是考虑加入新字符之后左半边会不会有 ‘套娃’ ，也就是可以将左半边的某个回文子串先添加一半再翻转（这里就用到了trans数组，当然是越长的回文子串越好了），然后剩余的部分用操作1继续添加，最后把左半边用操作2形成整个串，也就是dp[now]=dp[trans[now]]+(len[now] / 2-len[trans[now]])+1。每次新建结点的时候都要更新答案ans，因为dp数组记录的是长度为len[now]的串的最少步数，所以要用dp[now]+length-len[now]来更新。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define ll long long 6 #define ull unsigned long long 7 using namespace std; 8 9 const int MAXN = 1e5+10 ; 10 const int N = 26 ; 11 char str[MAXN]; 12 int dp[MAXN],trans[MAXN]; 13 int ans=0; 14 15 struct Palindromic_Tree { 16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成 17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点 18 int len[MAXN] ;//表示节点i表示的回文串的长度 19 int S[MAXN] ;//存放添加的字符 20 int last ;//指向上一个字符所在的节点，方便下一次add 21 int n ;//字符数组指针 22 int p ;//节点指针 23 24 int newnode ( int l ) {//新建节点 25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ; 26 len[p] = l ; 27 return p ++ ; 28 } 29 30 void init () {//初始化 31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点 32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/ 33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/ 34 last = 0 ; 35 n = 0 ; 36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 37 fail[0] = 1 ; 38 } 39 40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的 41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x]; 42 return x ; 43 } 44 45 void add ( int c ,int length) { 46 c -= 'A' ; 47 S[++ n] = c ; 48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 50 int now = newnode ( len[cur] + 2 ) ;//新建节点 51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 52 nt[cur][c] = now ; 53 if(len[now]>2){ 54 int x=trans[cur]; 55 while(S[n-len[x]-1]!=S[n]||(len[x]+2)*2>len[now]) x=fail[x]; 56 trans[now]=nt[x][c]; 57 } 58 else trans[now]=fail[now]; 59 dp[now]=len[now]; 60 if(len[now]%2==0){ 61 dp[now]=min(dp[now],dp[cur]+1); 62 dp[now]=min(dp[now],dp[trans[now]]+1+(len[now]/2-len[trans[now]])); //从上一个结点添加+1或者从fail那开始添加到一半然后翻转 63 ans=min(ans,dp[now]+length-len[now]); //dp[now]是当前长度回文串的最少步数，总步数是长度减当前回文串长度加步数。 64 } 65 } 66 last = nt[cur][c] ; 67 } 68 }pt; 69 70 int main() 71 { 72 int t; 73 scanf("%d",&t); 74 while(t--){ 75 memset(trans,0,sizeof(trans)); 76 memset(dp,0,sizeof(dp)); 77 scanf("%s",str); 78 int len=strlen(str); 79 pt.init(); 80 ans=len; 81 dp[0]=1; 82 for(int i=0;i<len;i++) pt.add(str[i],len); 83 printf("%d\n",ans); 84 } 85 return 0; 86 }
