Bzoj 3654 图样图森波题解

3654: 图样图森破

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 123 Solved: 66
[Submit][Status][Discuss]

Description

有句老话说得好，人应该要成熟老练，也就是说不能 too simple，也不能 too young。但另外还有这么句老话，人无论何时都应该保持单纯而年轻的心态，换句话说，应该stay simple，stay young。
于是人们就疑惑了，到底应不应该听长者的话呢？不过，不管听还是不听，这与本题都没有任何关系。
长者有一个字符串集合S，此处集合的概念与数学中的集合不同，其中可以含有重复的元素。初始时 S 包含 n 个字符串 s1;s2;:::;sn。有下面两种操作：
• 向S 中加入一个已经存在于 S 中的字符串。
• 从S 中选出两个字符串，将这两个字符串拼接得到的字符串加入集合 S。
长者想要知道，进行任意多次操作之后，在S 中的所有字符串中，最长的回文子串可以有多长？长者毕竟身经百战，他发现长度可以是无穷大，这时你需要输出Infinity。

Input

第一行含有一个整数 n，代表初始时集合的大小。
接下来的n行，每行含有一个字符串。第i行的字符串为si。保证字符串中只含有小写英文字母。

Output

如果最长的回文子串的长度不为无穷大，则输出一个整数，代表其长度；否则输出Infinity。

Sample Input

3
abc
abacde
ecab

Sample Output

HINT

第一个样例中，将ecab与abacde拼接，得到ecababacde，其中加粗的部分就是最长的回文子串，长度为 7。可以证明不存在更长的回文子串。第二个样例中，可以将任意多个ha拼接起来，从而得到ha、haha、hahaha等任意奇数长度的回文子串。因此答案为无穷大，输出Infinity。

N<=100

L<=1000

　　好恶心……

　　这道题貌似打法还挺多的，我就说一下记忆化搜索这种打法好了……

　　我们考虑最为“正常”的答案来源，就是几个串拼接在一起，我们尝试从回文串的中心去向外“扩增”回文串，我们可以先枚举每一个串的起始和末尾，因为如果想通过连接形成回文串的话必定会包括回文串的起始或末尾，我们尝试着利用这点和记忆化搜索得到答案。我们设0为从当前点向右的串去找串的右端点进行回文匹配，1为从当前点向左的串找串的左端点进行匹配，由于1和0本质一样，在这里就只说0的情况了。

　　我们枚举每一个串的末尾，将它与当前字符及其右进行匹配，这里有一点需要理解，尽管我们找的是串的末尾，但是当前点却不一定是串的起始，它也可能是某个回文串（回文串左端点恰好是一个串的左端点）右侧的第一个不匹配的点，我们找的那个串是为了将那个串拼在回文串的左侧对称的。那么问题来了，怎么找一个正串和一个反串的最大匹配呢？这里就可以用一个骚操作了，我们将所有串连在一起后集体反向，组成一个大串，然后求后缀数组，再RMQ就可以做到O(1)查询两个串的公共子串了。

　　最后我们不要忘记算单个串对于答案的贡献，原理还是一样，只不过改为自己和自己匹配以及自己和自己右侧的匹配。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <queue>
  8 #define N 3005
  9 #define M 100005
 10 using namespace std;
 11 int s[M*2],st[105],en[105],rnk[M*2],hi[M*2],SA[M*2],tp[M*2];
 12 int cnt[N],f[20][M*2],mn[M*2];
 13 void Rsort(int m,int n)
 14 {
 15     for(int i=0;i<=m;i++) cnt[i]=0;
 16     for(int i=1;i<=n;i++) cnt[rnk[tp[i]]]++;
 17     for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
 18     for(int i=n;i;i--) SA[cnt[rnk[tp[i]]]--]=tp[i];
 19 }
 20 bool cmp(int w,int x,int y)
 21 {
 22     return tp[x]==tp[y]&&tp[x+w]==tp[y+w];
 23 }
 24 void init(int n,int m)
 25 {
 26     for(int i=1;i<=n;i++) rnk[i]=s[i],tp[i]=i;
 27     Rsort(m,n);
 28     for(int i,w=1,p=0;p<n;m=p,w<<=1)
 29     {
 30         p=0;
 31         for(i=n-w+1;i<=n;i++) p++,tp[p]=i;
 32         for(i=1;i<=n;i++) if(SA[i]>w) p++,tp[p]=SA[i]-w;
 33         Rsort(m,n);
 34         swap(rnk,tp);
 35         rnk[SA[1]]=p=1;
 36         for(i=2;i<=n;i++) rnk[SA[i]]=cmp(w,SA[i],SA[i-1])?p:++p;
 37     }
 38     for(int i=1,k=0,j;i<=n;hi[rnk[i++]]=k)
 39         for(k=k?k-1:k,j=SA[rnk[i]-1];s[i+k]==s[j+k];k++);
 40     for(int i=1;i<=n;i++) f[0][i]=hi[i];
 41     for(int i=1;i<=18;i++)
 42     {
 43         for(int k=1;k<=n&&k+(1<<i)-1<=n;k++)
 44         {
 45             f[i][k]=(f[i-1][k]>f[i-1][k+(1<<(i-1))])?f[i-1][k+(1<<(i-1))]:f[i-1][k];
 46         }
 47     }
 48     mn[1]=0;
 49     for(int i=2;i<=n;i++)
 50     {
 51         mn[i]=mn[i-1];
 52         if(i==(1<<(mn[i]+1))) mn[i]++;
 53     }
 54 }
 55 int g[M*2][2],m,n,bel[M*2];
 56 char bb[M];
 57 bool fw[M*2][2];
 58 void inf_end()
 59 {
 60     printf("Infinity
");
 61     exit(0);
 62 }
 63 int get_min(int x,int y)
 64 {
 65     if(x==y) return M;
 66     x=rnk[x],y=rnk[y];
 67     if(x>y) swap(x,y);
 68     x++;
 69     int k=mn[y-x+1];
 70     return min(f[k][x],f[k][y-(1<<k)+1]);
 71 }
 72 int get_lcp(int x,int y)
 73 {
 74     return min(get_min(x,n-y+1),min(en[bel[x]]-x+1,y-st[bel[y]]+1));
 75 }
 76 int dfs(int x,int op)
 77 {
 78     if(fw[x][op]) inf_end();
 79     if(g[x][op]) return g[x][op];
 80     fw[x][op]=1;
 81     if(!op)
 82     {
 83         for(int i=1;i<=m;i++)
 84         {
 85             int k=get_lcp(x,en[i]);
 86             int xx,yy;
 87             xx=x+k-1,yy=en[i]-k+1;
 88             if(xx!=en[bel[x]]&&yy!=st[i]) g[x][op]=max(g[x][op],k*2);
 89             else if(xx==en[bel[x]]&&yy==st[i]) inf_end();
 90             else if(xx==en[bel[x]]) g[x][op]=max(g[x][op],k*2+dfs(yy-1,1));
 91             else g[x][op]=max(g[x][op],k*2+dfs(xx+1,0));
 92         }
 93     }
 94     else
 95     {
 96         for(int i=1;i<=m;i++)
 97         {
 98             int k=get_lcp(st[i],x);
 99             int xx,yy;
100             xx=x-k+1,yy=st[i]+k-1;
101             if(xx!=st[bel[x]]&&yy!=en[i]) g[x][op]=max(g[x][op],k*2);
102             else if(xx==st[bel[x]]&&yy==en[i]) inf_end();
103             else if(xx==st[bel[x]]) g[x][op]=max(g[x][op],k*2+dfs(yy+1,0));
104             else g[x][op]=max(g[x][op],k*2+dfs(xx-1,1));
105         }
106     }
107     fw[x][op]=0;
108     return g[x][op];
109 }
110 int ans;
111 int main()
112 {
113     scanf("%d",&m);
114     for(int i=1;i<=m;i++)
115     {
116         scanf("%s",bb+1);
117         int len=strlen(bb+1);
118         st[i]=n+1;
119         for(int j=1;j<=len;j++)
120         {
121             n++;
122             s[n]=bb[j]-'a'+1;
123             bel[n]=i;
124         }
125         en[i]=n;
126     }
127     for(int i=n+1,j=n;i<=n*2;i++,j--) s[i]=s[j];
128     n<<=1;
129     init(n,26);
130     for(int i=1;i<=m;i++)
131     {
132         ans=max(ans,dfs(st[i],0));
133         ans=max(ans,dfs(en[i],1));
134     }
135     for(int i=1;i<=m;i++)
136     {
137         for(int j=st[i];j<=en[i];j++)
138         {
139             int k=get_lcp(j,j);
140             int xx=j+k-1,yy=j-k+1;
141             if(xx!=en[i]&&yy!=st[i]) ans=max(ans,k*2-1);
142             else if(xx==en[i]&&yy==st[i]) inf_end();
143             else if(xx==en[i])ans=max(ans,k*2-1+dfs(yy-1,1));
144             else ans=max(ans,k*2-1+dfs(xx+1,0));
145         }
146         for(int j=st[i];j<en[i];j++)
147         {
148             int k=get_lcp(j+1,j);
149             int xx=j-k+1,yy=j+1+k-1;
150             if(xx!=st[i]&&yy!=en[i]) ans=max(ans,k*2);
151             else if(xx==st[i]&&yy==en[i]) inf_end();
152             else if(xx==st[i])ans=max(ans,k*2+dfs(yy+1,0));
153             else ans=max(ans,k*2+dfs(xx-1,1));
154         }
155     }
156     printf("%d
",ans);
157     return 0;
158 }

View Code