【GDOI 2014】beyond

2019-11-06 08:44:14

字体：大中小

来源：转载

供稿：网友

Description

给出两个串，求循环同构的最长前缀长度 1 <= N <= 2,000,000

Analysis

A,B两个串循环同构，大概就如下图，两个串红色部分，白色部分分别相等判断相等的话容易想到用扩展KMP的ext数组给两个串互相做扩展KMP，得到exta，extb 这里写图片描述

如果枚举A串分界点i $i$ ，如果B串存在一个位置j $j$ ，满足约束

j<=exta[i] $j<=exta[i]$ extb[j]>=i $extb[j]>=i$

则可以更新答案i+j $i+j$ 我们的任务其实就是对于每个i $i$ 求出最大的j $j$ 朴素的做法是让j从exta[i]到1搜一遍，找到第一个extb[j]>=i的位置pos 注意到第二个约束i $i$ 是递增的，那么对于以后再从pos+1~exta[i]开始，就可以直接跳到pos位置去（想一想为什么）这相当于一个指针指过去，而且带有并查集思想的路径压缩

Code

#include<cstdio>#include<cstring>#include<algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;const int N=2000005;char s1[N],s2[N];int n,f[N],nxt[N],ext1[N],ext2[N];void exkmp(char *a,char *b,int *c){ memset(nxt,0,sizeof(nxt)); memset(c,0,sizeof(c)); nxt[1]=n; int p=0,mx=0; fo(i,2,n) { nxt[i]=nxt[i-p+1]; if(i+nxt[i]>mx) { nxt[i]=max(0,mx-i+1); while(i+nxt[i]<=n && b[i+nxt[i]]==b[nxt[i]+1]) nxt[i]++; p=i,mx=i+nxt[i]-1; } } p=mx=0; fo(i,1,n) { c[i]=nxt[i-p+1]; if(i+c[i]>mx) { c[i]=max(0,mx-i+1); while(i+c[i]<=n && a[i+c[i]]==b[c[i]+1]) c[i]++; p=i,mx=i+c[i]-1; } }}int getfa(int v,int k){ if(!v) return 0; if(ext2[v+1]>=k) return v; else return f[v]=getfa(f[v],k);}int main(){ scanf("%d/n%s/n%s",&n,s1+1,s2+1); exkmp(s1,s2,ext1); exkmp(s2,s1,ext2); int ans=0; fo(i,1,n) f[i]=i-1; fo(i,1,n) { int x=getfa(ext1[i],i-1); if(x) ans=max(ans,i+x-1); } PRintf("%d",ans); return 0;}

上一篇：智能手机双摄像头原理解析：广角+长焦

下一篇：OpenCv (正式篇) 5----Highgui板块 /* 不断更新 */

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注