2020-2021:teams:legal_string:王智彪:回文自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:回文自动机 [2021/08/01 20:24] 王智彪 |
2020-2021:teams:legal_string:王智彪:回文自动机 [2021/08/01 22:28] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 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/王智彪/回文自动机.1627820699.txt.gz · 最后更改: 2021/08/01 20:24 由 王智彪
