#回文自动机#洛谷 3649 JZOJ 3654 回文串

2024-02-11 05:18

本文主要是介绍#回文自动机#洛谷 3649 JZOJ 3654 回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给你一个由小写拉丁字母组成的字符串 s s s。我们定义 s s s的一个子串的存在值为这个子串在 s s s中出现的次数乘以这个子串的长度。对于给你的这个字符串 s s s,求所有回文子串中的最大存在值。


分析

回文自动机模板,不解释


代码

#include <cstdio>
#include <cstring>
#define rr register
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=300011; char s[N]; int length,n; long long ans;
struct Trie{int trie[27],fail,len,s;};
struct PAM{Trie h[N]; int lst,cnt;inline void init(){h[0].len=h[1].fail=lst=0,h[0].fail=cnt=1,h[1].len=-1;}inline signed gail(int now){for (;s[n-h[now].len-1]^s[n];now=h[now].fail); return now;}inline void Insert(){rr int now=gail(lst);if (!h[now].trie[s[n]^96]){h[++cnt].len=h[now].len+2;rr int t=gail(h[now].fail);h[cnt].fail=h[t].trie[s[n]^96];h[now].trie[s[n]^96]=cnt;}lst=h[now].trie[s[n]^96];++h[lst].s;}
}pam;
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
signed main(){scanf("%s",s+1),length=strlen(s+1);s[0]=96,pam.init();for (n=1;n<=length;++n) pam.Insert();for (rr int i=pam.cnt;i;--i){pam.h[pam.h[i].fail].s+=pam.h[i].s;ans=max(ans,1ll*pam.h[i].s*pam.h[i].len);}return !printf("%lld",ans);
}

这篇关于#回文自动机#洛谷 3649 JZOJ 3654 回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/698930

相关文章

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

POJ 1625 自动机

给出包含n个可见字符的字符集,以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串,求长为m且不包含上述p个字符串的字符串有多少个。 g++提交 int mat[108][108] ;int matn ;int N ;map<char ,int> to ;//ACconst int maxm = 108 ;const int kin

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

正规式与有限自动机例题

答案:D 知识点: 正规式 正规集 举例 ab 字符串ab构成的集合 {ab} a|b 字符串a,b构成的集合 {a,b} a^* 由0或者多个a构成的字符串集合 {空,a,aa,aaa,aaaa····} (a|b)^* 所有字符a和b构成的串的集合 {空,a,b,ab,aab,aba,aaab····} a(a|b)^* 以a为首字符的a,b字符串的集

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

NYOJ 37 回文字符串(记忆化搜索)

OJ题目 : 戳这里~~ 描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。 输入 第一行给出整数N(0<N<100) 接下来的N行,每行一个字符串,每个字符串长度不超过1000.