COJ977 WZJ的数据结构(负二十三)

时间:2022-03-24 09:58:08
试题描述

输入一个字符串S,输出S的最长连续回文子串长度。

输入
输入一个字符串S。
输出
输出S的最长连续回文子串长度
输入示例
abacbbc
输出示例
4
其他说明
1<=|S|<=1000000

这就是传说中的萌萌哒马拉车算法(manacher)啦

首先为了方便处奇偶两种情况,将S重新变成新的字符串T,如abacddc变成#a#b#a#c#d#d#c#

再次为了方便处理越界,将字符串首尾加一个奇怪的不匹配字符,如将abacddc变成~#a#b#a#c#d#d#c#`

请大家想一想这样的好处

考虑暴力算法,枚举回文串中心,暴力向两边匹配

rep(,n-) {
int t=;
while(s[i-t]==s[i+t]) t++;
ans=max(ans,t-);
}

这样是O(N^2),考虑优化

我们定义P[i]表示位置i的最长匹配长度,考虑利用之前的匹配信息。

COJ977 WZJ的数据结构(负二十三)

这样就是p[i]=p[2*id-i]

COJ977 WZJ的数据结构(负二十三)

这样就是p[i]=mx-i

写成代码就是这样

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
char s[maxn];
int p[maxn];
int solve(char* s2) {
int n=,id=,mx=,ans=;
for(int i=;s2[i]!='\0';i++) s[n++]='#',s[n++]=s2[i];
s[]='~';s[n++]='#';s[n++]='`';
rep(,n-) {
if(mx>i) p[i]=min(p[*id-i],mx-i);
else p[i]=;
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i],id=i;
ans=max(ans,p[i]-);
}
return ans;
}
char s2[maxn];
int main() {
scanf("%s",s2);
printf("%d\n",solve(s2));
return ;
}

为什么是O(N)的呢?

因为算法只有遇到还没有匹配的位置时才进行匹配,已经匹配过的位置不再进行匹配,所以对于T字符串中的每一个位置,只进行一次匹配,所以Manacher算法的总体时间复杂度为O(n),其中n为T字符串的长度,由于T的长度事实上是S的两倍,所以时间复杂度依然是线性的。

补一个PAM的(以后不能装*,将”f[np]=to[k][c];to[p][c]=np;“i写成”f[to[p][c]=np]=to[k][c];“就会T飞,因为k可能等于p)

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
char ch[maxn];
struct PAM {
int cnt,last;
int to[maxn][],f[maxn],l[maxn];
PAM() {cnt=f[]=;l[]=-;}
void extend(int c,int n) {
int p=last;
while(ch[n]!=ch[n-l[p]-]) p=f[p];
if(!to[p][c]) {
int np=++cnt,k=f[p];l[np]=l[p]+;
while(ch[n]!=ch[n-l[k]-]) k=f[k];
f[np]=to[k][c];to[p][c]=np;
}
last=to[p][c];
}
int solve() {
int ans=;
rep(,cnt) ans=max(ans,l[i]);
return ans;
}
}sol;
int main() {
scanf("%s",ch+);int n=strlen(ch+);
rep(,n) sol.extend(ch[i]-'a',i);
printf("%d\n",sol.solve());
return ;
}

COJ977 WZJ的数据结构(负二十三)的更多相关文章

  1. COJ 1002 WZJ的数据结构(二)(splay模板)

    我的LCC,LCT,Splay格式终于统一起来了... 另外..这个形式的Splay是标准的Splay(怎么鉴别呢?看Splay函数是否只传了一个变量node就行),刘汝佳小白书的Splay写的真是不 ...

  2. &lbrack;COJ0988&rsqb;WZJ的数据结构(负十二)

    [COJ0988]WZJ的数据结构(负十二) 试题描述 输入 见题目,注意本题不能用文件输入输出 输出 见题目,注意本题不能用文件输入输出 输入示例 输出示例 数据规模及约定 1≤N≤1500,M≤N ...

  3. COJ967 WZJ的数据结构(负三十三)

    WZJ的数据结构(负三十三) 难度级别:C: 运行时间限制:7000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你设计一个数据结构,完成以下功能: 给定一个大 ...

  4. COJ968 WZJ的数据结构(负三十二)

    WZJ的数据结构(负三十二) 难度级别:D: 运行时间限制:5000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 给你一棵N个点的无根树,边上均有权值,每个点上有 ...

  5. COJ 0967 WZJ的数据结构(负三十三)

    WZJ的数据结构(负三十三) 难度级别:E: 运行时间限制:7000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你设计一个数据结构,完成以下功能: 给定一个大 ...

  6. COJ 0979 WZJ的数据结构(负二十一)

    WZJ的数据结构(负二十一) 难度级别:C: 运行时间限制:5000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你实现一个数据结构,完成这样的功能: 给你一个 ...

  7. &lbrack;COJ0968&rsqb;WZJ的数据结构(负三十二)

    [COJ0968]WZJ的数据结构(负三十二) 试题描述 给你一棵N个点的无根树,边上均有权值,每个点上有一盏灯,初始均亮着.请你设计一个数据结构,回答M次操作. 1 x:将节点x上的灯拉一次,即亮变 ...

  8. &lbrack;COJ0985&rsqb;WZJ的数据结构(负十五)

    [COJ0985]WZJ的数据结构(负十五) 试题描述 CHX有一个问题想问问大家.给你一个长度为N的数列A,请你找到两个位置L,R,使得A[L].A[L+1].…….A[R]中没有重复的数,输出R- ...

  9. &lbrack;COJ0989&rsqb;WZJ的数据结构(负十一)

    [COJ0989]WZJ的数据结构(负十一) 试题描述 给出以下定义: 1.若子序列[L,R]的极差(最大值-最小值)<=M,则子序列[L,R]为一个均匀序列. 2.均匀序列[L,R]的权值为S ...

随机推荐

  1. 【原】iOS多线程之线程间通信和线程互斥

    线程间通信 1> 线程间通信分为两种 主线程进入子线程(前面的方法都可以) 子线程回到主线程 2> 返回主线程 3> 代码 这个案例的思路是:当我触摸屏幕时,会在子线程加载图片,然后 ...

  2. 这是我定位的Bug

    https://github.com/danielgindi/ios-charts/issues/406

  3. module&lowbar;init宏解析 linux驱动的入口函数module&lowbar;init的加载和释放

    linux驱动的入口函数module_init的加载和释放 http://blog.csdn.net/zhandoushi1982/article/details/4927579 void free_ ...

  4. QQ互联OAuth2&period;0 &period;NET SDK 发布以及网站QQ登陆示例代码

    OAuth: OAuth(开放授权)是一个开放标准,允许用户授权第三方网站访问他们存储在另外的服务提供者上的信息,而不需要将用户名和密码提供给第三方网站或分享他们数据的所有内容. QQ登录OAuth2 ...

  5. 简单的总结一下iOS面试中会遇到的问题

    1.线程是什么?进程是什么?二者有什么区别和联系?  一个程序至少有一个进程,一个进程至少有一个线程: 进程:一个程序的一次运行,在执行过程中拥有独立的内存单元,而多个线程共享一块内存 线程:线程是指 ...

  6. YII进行数据增删改查分析

    关于模型部分參考http://blog.csdn.net/buyingfei8888/article/details/40208729 控制器部分: <?php class GoodsContr ...

  7. 各种反演细节梳理&amp&semi;模板

    炫酷反演魔术课件byVFK stO FDF Orz(证明全有%%%) 莫比乌斯反演 \(F(n)=\sum\limits_{d|n}f(d)\Rightarrow f(n)=\sum\limits_{ ...

  8. matlab求导数

    clc; %清屏 clear; %清除变量 close all; %关闭 syms x; %定义变量,多个变量间用空格分离 f(x) = x^3; %原函数 res = diff(f(x),x,1); ...

  9. Sql Server与&period;Net&lpar;C&num;&rpar;中星期值对比

    最近发现Sql Server与.Net(C#)中星期值居然不匹配,倒不知道依哪一个了. 1.Sql Server declare @date datetime; set @date = '2017-0 ...

  10. &lbrack;错误记录&rsqb;python requests库 Response 判断坑

    在requests访问之后, 我直接判断resp的值, 如下: if resp: do something 发现当Response 为500的时候没有进入if分支, 检查源码,发现Response重写 ...