广东哪有做网赌网站,网站备案省份,网站模板 简洁,体育直播网站开发数据源获取正题
题目链接:https://www.luogu.com.cn/problem/P4287 题目大意
长度为nnn的字符串。定义wRw^RwR表示字符串www的翻转。
一个双倍回文可以表示为wwRwwRww^Rww^RwwRwwR且这是个回文串。
求最长的子串是双倍回文。 解题思路
我们在构建PAMPAMPAM的时候维护一个halfhalfhal…正题
题目链接:https://www.luogu.com.cn/problem/P4287 题目大意
长度为nnn的字符串。定义wRw^RwR表示字符串www的翻转。
一个双倍回文可以表示为wwRwwRww^Rww^RwwRwwR且这是个回文串。
求最长的子串是双倍回文。 解题思路
我们在构建PAMPAMPAM的时候维护一个halfhalfhalf表示该节点表示的回文串中一个长度小于该串长度的一半的一个最长的回文后缀。
维护的时候我们显然不能一个一个顺着failfailfail往上跳我们可以从其父节点的halfhalfhalf开始跳这样的时间复杂度就有保证。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e610;
int n,len[N],fail[N],next[N][26],half[N],cnt,ans;
char s[N];
int get_fail(int x,int n){for(;s[n-len[x]-1]!s[n];xfail[x]);return x;
}
void Make_PAM(){s[0]26;len[1]-1;fail[0]cnt1;int last0;for(int i1;in;i){int vals[i]-a;int xget_fail(last,i);if(!next[x][val]){len[cnt]len[x]2;int yget_fail(fail[x],i);fail[cnt]next[y][val];if(len[cnt]2)half[cnt]fail[cnt];else{int zhalf[x];while(s[i-len[z]-1]!s[i]||(len[z]2)*2len[cnt])zfail[z];half[cnt]next[z][val];}next[x][val]cnt;}lastnext[x][val];}return;
}
int main()
{scanf(%d%s,n,s1);Make_PAM();for(int i1;icnt;i)if(len[half[i]]*2len[i]!(len[half[i]]1))ansmax(ans,len[i]);printf(%d,ans);
}
