求回文子串的长度,mp[i]保存以i为中心的回文子串的半径(长度一半)
利用mx和id,避免重复暴力求解,达到O(n)的时间复杂度
预先填充一些无关紧要的字符
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int MAXN=31000000; char tmp[MAXN],s[MAXN]; int mp[MAXN]; int main(){ int t; // scanf("%d",&t); t=1; while(t--){ scanf("%s",tmp+1); memset(mp,0,sizeof(mp)); memset(s,0,sizeof(s)); int len=strlen(tmp+1); for(int i=1;i<=len;i++){ s[(i<<1)-1]='#'; s[(i<<1)]=tmp[i]; } s[(len<<1)+1]='#'; s[(len<<1)+2]='