秩序魔咒 题解

题意：求两个字符串的最长公共回文子串与个数。 ~~题面故事部分参考哈利波特与魔法少女小圆~~ ~~中二病发作结果~~ 本题为一道不算特别难的字符串省选题，~~其实很模板~~。 下面分$Subtask$进行解析。 $Subtask1$ 判断输入是否为样例，如果是，输出即可。当然也可以不考虑此$Subtask$，因为分值为$0$。 $Subtask2$ 两串由同一字符组成，显然最长公共回文子串为长度较短的字符串整串。 $Subtask3$ 枚举两个串的子串（$O(n^2m^2)$），判断两子串是否相同（$O(\min(n,m))$），再判断子串是否为回文串（$O(\min(n,m))$），总时间复杂度为（$O(n^2m^2\min(n,m)$）。 $Subtask4$ 由于回文串左右对称，则必有一回文中心，以此中心为对称点左右两段字符串相同。分奇数偶数两种情况讨论，在两个串中枚举回文中心，由中心出发检查能使左右相同的最大长度。复杂度$O(nm\min(n,m))$。 $Subtask5$ 优化$Subtask4$中的做法。考虑字符串哈希，枚举回文中心后二分回文串长度，并检查四段字符串（一串中心左，一串中心右，二串中心左，二串中心右）是否都相同。 还需要回避相同回文串重复计数的问题。让哈希取模数小至可以开下数组，以其大小开$bool$数组。每当找到回文串时看看$bool$数组中是否已经记录了此回文串，之后将$bool$数组中此回文串哈希值处设为$true$。复杂度$O(nm\log(\min(n,m)))$ $Subtask6$ 可以转化成求一个字符串的最长回文子串，是[[APIO2014]回文串](https://www.luogu.org/problem/P3649)的弱化版，可以使用马拉车，回文自动机，后缀自动机等方法通过。具体方法不给出，请大家参考上文提到题目的题解或下文$Subtask7$的题解。 update:出题人在考虑数据的时候竟然忘了此部分分数可以被$hash$水过qaq。那么此题用$hash$来做就有$60$分了。 $Subtask7$ ~~据大佬说似乎也可以用回文自动机通过，不过本人太弱了，不会~~ 考虑将此题拆解成最长回文子串和最长公共子串两个问题来思考。最长回文子串的做法$Subtask6$已提到，可以用马拉车，回文自动机，$SAM$等方法做。而最长公共子串可以用$SA$，$SAM$等方法做。 我们考虑用$SAM$解决此题。首先考虑如何解决最长回文子串问题。我们把反串拼在正串后面。我们知道，$SAM$两个前缀的最长后缀就是两个前缀属于的节点在parent tree上的$lca$。所以，我们先枚举回文中心，每个回文中心在正串和反串上分别有一个对应点。我们找到它们的$lca$，即找到了以此回文中心为中心的回文串的最长长度。举个例子，字符串$aababb$，正反串拼接后为$aababbAbbabaa$（中间为特殊字符，防止出现问题）。我们找以第四个字符（$aaba$最后的$a$）为回文中心的最长回文子串。此回文中心在反串中对应的位置为第$10$个（$aababbAbba$最后的$a$）。两个位置的$lca$的最长$len$为$2$（$ba$），又因为此况回文串长度为奇数，所以以此回文中心为中心的回文串长度最长为$2*2-1=3$（$bab$）。 有了以上做法，我们考虑本题做法。首先将一串正反拼接，然后将二串正反拼接在一串的正反拼接之后。首先求出一串和二串中所有的$lca$，在节点上打上标记。显然，如果一个节点可以作为一个回文串的一边（$lca$找到的是回文串的左边），那么其在parent tree上的父亲节点也可以作为以同一个回文中心为中心的回文串的一边。那么，我们$dfs$整颗parent tree，如果一个节点的儿子节点有标记，那么也给这个节点打上标记。之后对于每个节点，判断是否两个串都在其上有标记（此回文串在两个串中都有出现），如果有，则看看标记的类型，分奇偶处理完整回文串长度。这样，时间复杂度为$O((n+m)\log(n+m))$。（$\log$为处理$lca$的复杂度） 标程： ``` #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<iostream> using namespace std; const int SAM=2100000; struct NODE { int ch[29]; int fa,len; NODE(){memset(ch,0,sizeof(ch));fa=len=0;} }dian[SAM]; int las=1,js=1; int zx[2][300000],fx[2][300000],zxgs[2]={0},fxgs[2]={0}; bool tag[2][2][SAM]; struct Edge { int t,nexty; }edge[SAM]; int head[SAM],cnt=0; inline void add(int a,int b) { cnt++; edge[cnt].t=b; edge[cnt].nexty=head[a]; head[a]=cnt; } inline void zj(int c,int ope) { int p=las;int np=las=++js; if(ope==1)zx[0][++zxgs[0]]=las; if(ope==2)fx[0][++fxgs[0]]=las; if(ope==3)zx[1][++zxgs[1]]=las; if(ope==4)fx[1][++fxgs[1]]=las; dian[np].len=dian[p].len+1; for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np; if(!p)dian[np].fa=1; else { int q=dian[p].ch[c]; if(dian[q].len==dian[p].len+1)dian[np].fa=q; else { int nq=++js;dian[nq]=dian[q]; dian[nq].len=dian[p].len+1; dian[np].fa=dian[q].fa=nq; for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq; } } } int fa[SAM]={0},sz[SAM]={0},son[SAM]={0},lianfa[SAM]={0},dep[SAM]={0}; void dfs1(int node) { sz[node]=1; for(int i=head[node];i;i=edge[i].nexty) { fa[edge[i].t]=node;dep[edge[i].t]=dep[node]+1; dfs1(edge[i].t); sz[node]+=sz[edge[i].t]; if(sz[son[node]]<sz[edge[i].t])son[node]=edge[i].t; } } void dfs2(int node,int lf) { lianfa[node]=lf; if(son[node])dfs2(son[node],lf); for(int i=head[node];i;i=edge[i].nexty) { if(edge[i].t==son[node])continue; dfs2(edge[i].t,edge[i].t); } } int qlca(int a,int b) { while(lianfa[a]!=lianfa[b]) { if(dep[lianfa[a]]<dep[lianfa[b]])swap(a,b); a=fa[lianfa[a]]; } if(dep[a]>dep[b])swap(a,b); return a; } char s1[300000],s2[300000]; int n1,n2; int maxlen=0,num=0; void dfs(int node) { for(int i=head[node];i;i=edge[i].nexty) { dfs(edge[i].t); tag[0][0][node]|=tag[0][0][edge[i].t]; tag[0][1][node]|=tag[0][1][edge[i].t]; tag[1][0][node]|=tag[1][0][edge[i].t]; tag[1][1][node]|=tag[1][1][edge[i].t]; } int lc; if(tag[0][0][node]&&tag[1][0][node]) { lc=dian[node].len*2-1; if(maxlen==lc)num++; if(maxlen<lc)maxlen=lc,num=1; } if(tag[0][1][node]&&tag[1][1][node]) { lc=dian[node].len*2; if(maxlen==lc)num++; if(maxlen<lc)maxlen=lc,num=1; } } int main() { scanf("%d%d%s%s",&n1,&n2,s1,s2); for(int i=0;i<n1;i++)zj(s1[i]-'a',1); zj('z'-'a'+1,0); for(int i=0;i<n2;i++)zj(s2[i]-'a',3); zj('z'-'a'+2,0); for(int i=n2-1;i>=0;i--)zj(s2[i]-'a',4); zj('z'-'a'+3,0); for(int i=n1-1;i>=0;i--)zj(s1[i]-'a',2); for(int i=2;i<=js;i++){add(dian[i].fa,i);} dep[1]=1; dfs1(1);dfs2(1,1); int a,b; for(int i=1;i<=zxgs[0];i++)//case0 0 { a=zx[0][i];b=fx[0][fxgs[0]-i+1]; a=qlca(a,b);tag[0][0][a]=true; } for(int i=1;i<zxgs[0];i++)//case0 1 { a=zx[0][i];b=fx[0][fxgs[0]-i]; a=qlca(a,b);tag[0][1][a]=true; } for(int i=1;i<=zxgs[1];i++)//case1 0 { a=zx[1][i];b=fx[1][fxgs[1]-i+1]; a=qlca(a,b);tag[1][0][a]=true; } for(int i=1;i<zxgs[1];i++)//case1 1 { a=zx[1][i];b=fx[1][fxgs[1]-i]; a=qlca(a,b);tag[1][1][a]=true; } dfs(1); printf("%d %d\n",maxlen,num); return 0; } ``` [标程提交记录](https://www.luogu.org/record/23661066)，以此证明出题人不卡常（求勿喷）。