POJ3415:Common Substrings——题解

时间:2021-07-14 05:13:55

http://poj.org/problem?id=3415

给定两个字符串A 和B,求长度不小于k 的公共子串的个数(可以相同)。

论文题,和上道题(POJ2774)类似,首先想到现将AB串合并,然后子串可以表示成字符串后缀的前缀,于是我们比较任意两个A后缀和B后缀,用height求出他们的公共子串长度就很好做了。

(不懂为什么好做的可以看SPOJ694

那么最坏的想法就是每遇到B后缀就和前面遇到的A后缀比较,这样显然TLE,也没用到height数组的优越性。

但是我们A后缀可以用单调栈维护,这样复杂度即可。

(大致细节:对照代码,tot是暂时存答案的地方,当遇到height数组比单调栈顶小时开始弹出,同时高出height的部分要从tot被扣掉(注意要扣掉(二者之间的后缀数)次,因为他们都重复计算了),只有当A前缀出现的时候才能用tot更新ans)

同理再对A后缀做一遍如上操作,两次答案之和即为最终所求。

(感觉是懂了,还是迷迷糊糊的,可以看这个:https://www.cnblogs.com/CSU3901130321/p/4516109.html

(其实最关键的是两个后缀的公共前缀是他们排名之间所有的height的最小值,所以一遇到变低的height就需要更新了,并且说明之前的所有都被多算了。)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+;
char s[N];
int n,m,len,rank[N],sa[N],height[N],w[N];
inline bool pan(int *x,int i,int j,int k){
int ti=i+k<n?x[i+k]:-;
int tj=j+k<n?x[j+k]:-;
return x[i]==x[j]&&ti==tj;
}
inline void SA_init(){
int *x=rank,*y=height,r=;
for(int i=;i<r;i++)w[i]=;
for(int i=;i<n;i++)w[s[i]]++;
for(int i=;i<r;i++)w[i]+=w[i-];
for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;
r=;x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;
for(int k=;r<n;k<<=){
int yn=;
for(int i=n-k;i<n;i++)y[yn++]=i;
for(int i=;i<n;i++)
if(sa[i]>=k)y[yn++]=sa[i]-k;
for(int i=;i<r;i++)w[i]=;
for(int i=;i<n;i++)++w[x[y[i]]];
for(int i=;i<r;i++)w[i]+=w[i-];
for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];
swap(x,y);r=;x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;
}
for(int i=;i<n;i++)rank[i]=x[i];
}
inline void height_init(){
int i,j,k=;
for(i=;i<=n;i++)rank[sa[i]]=i;
for(i=;i<n;i++){
if(k)k--;
else k=;
j=sa[rank[i]-];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
ll ans,tot;
int q[N][],top;
ll solve(){
ans=tot=top=;
for(int i=;i<=n;i++){
if(height[i]<m)top=tot=;
else{
int cnt=;
if(sa[i-]<len)cnt++,tot+=height[i]-m+;
while(top>&&height[i]<=q[top-][]){
top--;
tot-=q[top][]*(q[top][]-height[i]);
cnt+=q[top][];
}
q[top][]=height[i];q[top++][]=cnt;
if(sa[i]>len)ans+=tot;
}
}
tot=top=;
for(int i=;i<=n;i++){
if(height[i]<m)top=tot=;
else{
int cnt=;
if(sa[i-]>len)cnt++,tot+=height[i]-m+;
while(top>&&height[i]<=q[top-][]){
top--;
tot-=q[top][]*(q[top][]-height[i]);
cnt+=q[top][];
}
q[top][]=height[i];q[top++][]=cnt;
if(sa[i]<len)ans+=tot;
}
}
return ans;
}
int main(){
while(scanf("%d",&m)!=EOF&&m){
scanf("%s",s);
len=n=strlen(s);
s[n++]=;
scanf("%s",s+n);
n=strlen(s);
s[n++]=;
SA_init();
n--;
height_init();
printf("%lld\n",solve());
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

POJ3415:Common Substrings——题解的更多相关文章

  1. POJ3415 Common Substrings —— 后缀数组 &plus; 单调栈 公共子串个数

    题目链接:https://vjudge.net/problem/POJ-3415 Common Substrings Time Limit: 5000MS   Memory Limit: 65536K ...

  2. POJ3415 Common Substrings&lpar;后缀数组 单调栈&rpar;

    借用罗穗骞论文中的讲解: 计算A 的所有后缀和B 的所有后缀之间的最长公共前缀的长度,把最长公共前缀长度不小于k 的部分全部加起来.先将两个字符串连起来,中间用一个没有出现过的字符隔开.按height ...

  3. poj3415 Common Substrings(后缀数组,单调栈 &vert; 后缀自动机)

    [题目链接] http://poj.org/problem?id=3415 [题意] A与B长度至少为k的公共子串个数. [思路] 基本思想是将AB各个后缀的lcp-k+1的值求和.首先将两个字符串拼 ...

  4. POJ3415 Common Substrings

    后缀数组 求长度不小于k的公共子串的个数 代码: #include <stdio.h> #include <string.h> ; int len, len1; int wa[ ...

  5. 2018&period;12&period;15 poj3415 Common Substrings(后缀自动机)

    传送门 后缀自动机基础题. 给两个字符串,让你求长度不小于kkk的公共子串的数量. 这题可以用后缀自动机解决废话 考虑对其中一个字串建出后缀自动机,然后用另一个在上面跑,注意到如果一个状态有贡献的话, ...

  6. POJ3415 Common Substrings 【后缀数组 &plus; 单调栈】

    常见的子串 时间限制: 5000MS   内存限制: 65536K 提交总数: 11942   接受: 4051 描述 字符串T的子字符串被定义为: Ť(我,ķ)= Ť 我 Ť 我 1 ... Ť I ...

  7. poj3415 Common Substrings &lpar;后缀数组&plus;单调队列&rpar;

    Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 9414   Accepted: 3123 Description A sub ...

  8. 【POJ3415】 Common Substrings(后缀数组&vert;SAM)

    Common Substrings Description A substring of a string T is defined as: T(i, k)=TiTi+1...Ti+k-1, 1≤i≤ ...

  9. POJ 3415 Common Substrings(后缀数组 &plus; 单调栈)题解

    题意: 给两个串\(A.B\),问你长度\(>=k\)的有几对公共子串 思路: 先想一个朴素算法: 把\(B\)接在\(A\)后面,然后去跑后缀数组,得到\(height\)数组,那么直接\(r ...

随机推荐

  1. NPOI使用手册&lbrack;转&rsqb;

    NPOI使用手册 目录 1.认识NPOI 2. 使用NPOI生成xls文件 2.1 创建基本内容 2.1.1创建Workbook和Sheet 2.1.2创建DocumentSummaryInforma ...

  2. iOS实现图像素描效果

    使用GPUImageSketchFilter对象实现图像素描效果 NSString *const kGPUImageSketchFragmentShaderString = SHADER_STRING ...

  3. 在centos上使用yum安装redis及php扩展php-redis

    .wget http://mirrors.ustc.edu.cn/fedora/epel/6/x86_64/epel-release-6-8.noarch.rpm rpm -ivh epel-rele ...

  4. ios 设置label的高度随着内容的变化而变化

    好吧 步骤1:创建label _GeRenJianJie = [[UILabel alloc]init]; 步骤2:设置label _GeRenJianJie.textColor = RGBAColo ...

  5. iOS8 Core Image In Swift:自动改善图像以及内置滤镜的使用

    iOS8 Core Image In Swift:自动改善图像以及内置滤镜的使用 iOS8 Core Image In Swift:更复杂的滤镜 iOS8 Core Image In Swift:人脸 ...

  6. HTML5 input 类型: email及url

    原文地址:HTML5′s "email" and "url" Input Types 原文日期: 2010年09月15日 翻译日期: 2013年08月13日 在 ...

  7. BZOJ&lowbar;1030&lowbar;&lbrack;JSOI2007&rsqb;文本生成器&lowbar;AC自动机&plus;DP

    BZOJ_1030_[JSOI2007]文本生成器_AC自动机+DP Description JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群, 他 ...

  8. load data语句实验报告

    1.创建和选择数据库 如果管理员在设置权限时为您创建数据库,则可以开始使用它.否则,您需要自己创建它: 创建数据库不会选择它来使用; 你必须明确地这样做.要创建menagerie当前数据库,请使用以下 ...

  9. WebSocket 处理事件

    WebSocket 是 HTML5 开始提供的一种在单个 TCP 连接上进行全双工通讯的协议. WebSocket 使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据.在 W ...

  10. mac 安装 tomcat 配置

    前面的话:记录下 Mac 安装配置 Tomcat 过程 1. 下载安装 Tomcat 下载 Tomcat 地址(官方地址):https://tomcat.apache.org/download-80. ...