【SPOJ1811】Longest Common Substring(后缀自动机)
2024-09-06 01:20:12
题意:给定两个仅含小写字母的字符串,求他们最长公共子串的长度
n<=250000
思路:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,int>P;
#define N 510000
#define M 151000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const int MOD=,inv2=(MOD+)/;
double eps=1e-;
ll INF=1e18;
ll inf=5e13;
int dx[]={-,,,};
int dy[]={,,-,}; char s[N];
int n,i,x,p,q,np,nq,cnt,L,st[N],c[N][],f[N],pos[N],bl[N],to[N],b[N],sz[N]; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void add(int x)
{
p=np;
st[np=++cnt]=st[p]+;
to[np]=i;
pos[i]=np;
for(;p&&!c[p][x];p=f[p]) c[p][x]=np;
if(!p) f[np]=;
else if(st[p]+==st[q=c[p][x]]) f[np]=q;
else
{
st[nq=++cnt]=st[p]+;
memcpy(c[nq],c[q],sizeof c[q]);
f[nq]=f[q];
f[q]=f[np]=nq;
for(;p&&c[p][x]==q;p=f[p]) c[p][x]=nq;
}
} int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
np=cnt=;
scanf("%s",s);
n=strlen(s);
rep(i,,n-) add(s[i]-'a'); rep(i,,cnt) b[st[i]]++;
rep(i,,n) b[i]+=b[i-];
rep(i,,cnt) bl[b[st[i]]--]=i;
for(i=,p=;i<n;i++) sz[p=c[p][s[i]-'a']]++;
for(i=cnt;i;i--) sz[f[bl[i]]]+=sz[bl[i]];
//rep(i,0,n-1) printf("%d ",sz[pos[i]]);
scanf("%s",s);
n=strlen(s);
int ans=;
for(p=,L=i=;i<n;i++)
{
if(c[p][x=s[i]-'a']) p=c[p][x],L++;
else
{
for(;!c[p][x]&&p;p=f[p]);
if(!p) p=,L=;
else L=st[p]+,p=c[p][x];
}
ans=max(ans,L);
}
printf("%d\n",ans);
return ;
}
最新文章
- requirejs+angularjs搭建SPA页面应用
- Lable得到自定义高度!
- js中~~的用法
- sqlserver临时启用和关闭约束
- 空函数有参函数调用参数的注意事项Swift 1.1语言
- Redis 在新浪微博中的应用
- HDU 4586 A - Play the Dice 找规律
- PHP系列目录
- 单片AT89C2051 + SD卡 + 3310LCD = 音乐播放器
- Lambda 可以转换成委托或expression树
- day 04 list,元祖
- ASP.NET结合Redis实现分布式缓存
- go自动补全
- winform无边框窗体更改大小
- SQL Server中怎么查看每个数据库的日志大小,以及怎么确定数据库的日志文件,怎么用语句收缩日志文件
- MapReduce 图解流程超详细解答(1)-【map阶段】
- 【VI】如何再执行上一个(历史)命令(已解决)
- 利用 NGINX 最大化 Python 性能,第二部分:负载均衡和监控
- Spring Tools Suite (STS) 简介
- [AT2172] [agc007_e] Shik and Travel
热门文章
- redhat 修改yum源
- GitLab 安装,配置及维护
- tomcat中的server.xml文件配置了URIEncoding=";UTF-8";需要注意的问题
- MySQL-极恶安装
- vscode 在ubuntu的terminal中下划线不显示解决方案
- vue 使用 computed 结合 filter 实现数据的的过滤和排序
- [已解决]报错: Error response from daemon: conflict
- k8s应用配置详解
- jquery 获取多选select的文本中并拼接成字符串
- C# 面试 笔试题