北京 工业网站建设公司排名,做网站和平台多少钱,网站建设培训个人,网站设计的原始资料正题
题目链接:https://www.luogu.com.cn/problem/P3649 题目大意
一个字符串#xff0c;求最大的回文串长度出现次数 解题思路
构建出PAM\text{PAM}PAM然后统计一下每个节点作为后缀的次数#xff0c;failfailfail树上上传一下信息就好了#xff0c;时间复杂度O(n)O(n)O…正题
题目链接:https://www.luogu.com.cn/problem/P3649 题目大意
一个字符串求最大的回文串长度×出现次数 解题思路
构建出PAM\text{PAM}PAM然后统计一下每个节点作为后缀的次数failfailfail树上上传一下信息就好了时间复杂度O(n)O(n)O(n)。
当然也可以SAMManacher\text{SAM}\text{Manacher}SAMManacher倍增因为一个字符串里本质不同的回文串就是会让马拉车的maxrightmaxrightmaxright增加的回文串这些最多只有nnn个马拉车跑出来的丢到SAM\text{SAM}SAM倍增找到对应节点即可。时间复杂度O(nlogn)O(n\log n)O(nlogn)
这里写的是PAM\text{PAM}PAM code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e510;
int n,tot,fail[N],len[N],cnt[N],ch[N][26];
char s[N];long long ans;
int get_fail(int x,int n){for(;s[n-len[x]-1]!s[n];)xfail[x];return x;
}
int Insert(int n,int x){xget_fail(x,n);int cs[n]-a;if(!ch[x][c]){len[tot]len[x]2;int yget_fail(fail[x],n);fail[tot]ch[y][c];ch[x][c]tot;}cnt[ch[x][c]];return ch[x][c];
}
int main()
{scanf(%s,s1);nstrlen(s1);int last0;len[1]-1;fail[0]tot1;for(int i1;in;i)lastInsert(i,last);for(int itot;i1;i--)cnt[fail[i]]cnt[i];for(int i1;itot;i)ansmax(ans,1ll*len[i]*cnt[i]);printf(%lld\n,ans);
}
