2020-2021:teams:legal_string:王智彪:回文自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:回文自动机 [2021/08/01 20:25] 王智彪 |
2020-2021:teams:legal_string:王智彪:回文自动机 [2021/08/01 22:28] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 102: | 行 102: | ||
| 还有 $x$ 是一个回文串， $y$ 是 $x$ 的最长回文真后缀， $z$ 是 $y$ 的最长回文真后缀。令 $u,v$ 分别为满足 $x=uy,y=vz$ 的字符串，则有： | 还有 $x$ 是一个回文串， $y$ 是 $x$ 的最长回文真后缀， $z$ 是 $y$ 的最长回文真后缀。令 $u,v$ 分别为满足 $x=uy,y=vz$ 的字符串，则有： | ||
| - | $1)|u|≥|v|$ 。 | + | $1.|u|≥|v|$ 。 |
| 证明： $|u|=|x|-|y|$ ，是 $x$ 的最小周期，同样也是 $y$ 的周期，又因为 $v$ 是 $y$ 的最小周期，所以 $|u|≥|v|$ 。 | 证明： $|u|=|x|-|y|$ ，是 $x$ 的最小周期，同样也是 $y$ 的周期，又因为 $v$ 是 $y$ 的最小周期，所以 $|u|≥|v|$ 。 | ||
| - | $2)$ 如果 $|u|＞|v|$ ， $|u|＞|z|$ 。 | + | $2.$ 如果 $|u|＞|v|$ ， $|u|＞|z|$ 。 |
| - | $3)$ 如果 $|u|=|v|$ ， $u=v$ 。 | + | $3.$ 如果 $|u|=|v|$ ， $u=v$ 。 |
| 4.[[https://www.luogu.com.cn/problem/P4555]] | 4.[[https://www.luogu.com.cn/problem/P4555]] | ||
| 行 176: | 行 176: | ||
| } | } | ||
| printf("%d",ans); | printf("%d",ans); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 5.[[https://www.luogu.com.cn/problem/P4287]] | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给一个字符串 $S$ ，让求一个双倍回文串，这里的双倍回文串要求必须是 $RR^{T}RR^{T}$ 形式的。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 我们发现这样的子串长度一定是 $4$ 的倍数，并且不超过自己一半长度的最长的失配串的长度一定正好是一半。于是我们重新搞一个 $f$ 数组，记录不超过自己一半长度的最长失配串，如果在找 $fail$ 的时候，发现不到一半，直接赋值成 $fail$ 指针就好了，不然我们需要走 $fail$ 指针，直到长度不到一半为止。 | ||
| + | |||
| + | <hidden 题解> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | void solve() { | ||
| + | for(int i=0; i<=n-1; i++) { | ||
| + | pos=getfail(cur,i); | ||
| + | if(!trie[pos][s[i]-'a']) { | ||
| + | fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a']; | ||
| + | trie[pos][s[i]-'a']=tot; | ||
| + | len[tot]=len[pos]+2; | ||
| + | num[tot]=num[fail[tot]]+1; | ||
| + | if(len[fail[tot]]<=len[tot]>>1) f[tot]=fail[tot]; | ||
| + | else{ | ||
| + | int poss=f[pos];//仿照上面的 | ||
| + | while(len[poss]+2>len[tot]/2||s[i]!=s[i-len[poss]-1]) poss=fail[poss];//仿照上面的函数len[poss]是没加上两边的串所以再加上两边的大于一半就得跑fail指针 | ||
| + | f[tot]=trie[poss][s[i]-'a'];//仿照上面的 | ||
| + | } | ||
| + | } | ||
| + | cur=trie[pos][s[i]-'a']; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | p.init(); | ||
| + | int nn; | ||
| + | scanf("%d",&nn); | ||
| + | scanf("%s",p.s); | ||
| + | p.n=strlen(p.s); | ||
| + | p.solve(); | ||
| + | for(int i=2;i<=p.tot;i++){ | ||
| + | if(p.len[i]%4==0&&p.len[p.f[i]]==p.len[i]>>1){//长度正好是一半 | ||
| + | p.Ans=max(p.Ans,p.len[i]); | ||
| + | } | ||
| + | } | ||
| + | printf("%d\n",p.Ans); | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/王智彪/回文自动机.1627820740.txt.gz · 最后更改: 2021/08/01 20:25 由 王智彪
