后缀数组:HDU1043 Longest Common Substring

时间:2022-09-21 16:00:57

Longest Common Substring

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5375    Accepted Submission(s): 1910

Problem Description
Given two strings, you have to tell the length of the Longest Common Substring of them.

For example:
str1 = banana
str2 = cianaic

So the Longest Common Substring is "ana", and the length is 3.

 
Input
The input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case.

Process to the end of file.

 
Output
For each test case, you have to tell the length of the Longest Common Substring of them.
 
Sample Input
banana
cianaic
 
Sample Output
3
 
  这题求最长公共字串,简单的DP并不可以搞定,因为数据范围len<=10^5,所以我用后缀数组做的。
  这里将两个字符串连起来,中间用特殊符号隔开,只要两个在排序上连续的后缀的起点在断点两边,就用其更新答案。
 
 #include <iostream>
#include <cstring>
#include <cstdio> const int maxn=;
int Ws[maxn],Wv[maxn],Wa[maxn],Wb[maxn],lcp[maxn],sa[maxn],rank[maxn],r[maxn];
bool cmp(int *p,int i,int j,int l)
{return p[i]==p[j]&&p[i+l]==p[j+l];} void DA(int n,int m)
{
int i,j,p,*x=Wa,*y=Wb;
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)++Ws[x[i]=r[i]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)
sa[--Ws[x[i]]]=i;
for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)
if(sa[i]>=j)
y[p++]=sa[i]-j; for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)Wv[i]=x[y[i]];
for(i=;i<n;i++)++Ws[Wv[i]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[Wv[i]]]=y[i];
for(std::swap(x,y),p=,i=,x[sa[]]=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
}
void LCP(int n)
{
int i,j,k=;
for(i=;i<=n;i++)
rank[sa[i]]=i; for(i=;i<n;lcp[rank[i++]]=k)
for(k?--k:k,j=sa[rank[i]-];r[i+k]==r[j+k];k++);
}
char str1[maxn>>],str2[maxn>>];
int main()
{
int i,len1,len2,ans;
while(~scanf("%s",str1)){
for(len1=;str1[len1];len1++)
r[len1]=str1[len1];
r[len1]='$';
scanf("%s",str2);
for(len2=;str2[len2];len2++)
r[len1+len2+]=str2[len2];
DA(len1+len2+,);
LCP(len1+len2+);
ans=;
for(i=;i<len1+len2+;i++)
if(sa[i]<len1&&sa[i-]>len1||sa[i-]<len1&&sa[i]>len1)
ans=std::max(ans,lcp[i]);
printf("%d\n",ans);
}
return ;
}
 

后缀数组:HDU1043 Longest Common Substring的更多相关文章

  1. hdu 1403 Longest Common Substring&lpar;最长公共子字符串&rpar;(后缀数组)

    http://acm.hdu.edu.cn/showproblem.php?pid=1403 Longest Common Substring Time Limit: 8000/4000 MS (Ja ...

  2. HDU 1403 Longest Common Substring(后缀自动机——附讲解 or 后缀数组)

    Description Given two strings, you have to tell the length of the Longest Common Substring of them. ...

  3. spoj 1811 LCS - Longest Common Substring &lpar;后缀自己主动机&rpar;

    spoj 1811 LCS - Longest Common Substring 题意: 给出两个串S, T, 求最长公共子串. 限制: |S|, |T| <= 1e5 思路: dp O(n^2 ...

  4. Longest Common Substring II SPOJ - LCS2 (后缀自动机)

    Longest Common Substring II \[ Time Limit: 236ms\quad Memory Limit: 1572864 kB \] 题意 给出\(n\)个子串,要求这\ ...

  5. 【SPOJ】Longest Common Substring II (后缀自动机)

    [SPOJ]Longest Common Substring II (后缀自动机) 题面 Vjudge 题意:求若干个串的最长公共子串 题解 对于某一个串构建\(SAM\) 每个串依次进行匹配 同时记 ...

  6. 【SPOJ】Longest Common Substring(后缀自动机)

    [SPOJ]Longest Common Substring(后缀自动机) 题面 Vjudge 题意:求两个串的最长公共子串 题解 \(SA\)的做法很简单 不再赘述 对于一个串构建\(SAM\) 另 ...

  7. SPOJ1811 LCS - Longest Common Substring&lpar;后缀自动机&rpar;

    A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the s ...

  8. LCS2 - Longest Common Substring II&lpar;spoj1812&rpar;&lpar;sam&lpar;后缀自动机&rpar;&plus;多串LCS&rpar;

    A string is finite sequence of characters over a non-empty finite set \(\sum\). In this problem, \(\ ...

  9. SPOJ 1811&period; Longest Common Substring (LCS,两个字符串的最长公共子串, 后缀自动机SAM)

    1811. Longest Common Substring Problem code: LCS A string is finite sequence of characters over a no ...

随机推荐

  1. apache部署django记录

    在ubuntu下通过apache部署django 首先需要下载python,django,apache以及wsgi模块 python基本已经自带,我用的是2.7,不是的话可以重新装一个 下载djang ...

  2. Unity中对象池的使用

    unity中用到大量重复的物体,例如发射的子弹,可以引入对象池来管理,优化内存. 对象池使用的基本思路是: 将用过的对象保存起来,等下一次需要这种对象的时候,再拿出来重复使用.恰当地使用对象池,可以在 ...

  3. TortoiseGit保存用户名及密码

    保存密码方式如下,需要setting中填写自己的名字,Email地址,并在.gitconfig中 [credential] 中设置helper = store

  4. PHP – AJAX 与 PHP

    AJAX 被用于创建交互性更强的应用程序. AJAX PHP 实例 下面的实例将演示当用户在输入框中键入字符时,网页如何与 Web 服务器进行通信: 实例 尝试在输入框中输入一个名字,如:Anna: ...

  5. MVC View中获取action、controller、area名称、参数

    获取控制器名称: ViewContext.RouteData.Values["controller"].ToString(); 获取Action名称: ViewContext.Ro ...

  6. 在Mac OS环境下安装MySQL服务

    在Mac OS环境下安装MySQL服务 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任. 我之前介绍过window环境下安装mysql服务,以及在Linux环境下安装mysql服务,今 ...

  7. Docker孵化的5个开源项目

    版权声明:本文为博主原创文章.未经博主同意不得转载. https://blog.csdn.net/M2l0ZgSsVc7r69eFdTj/article/details/81977243 回想过去短短 ...

  8. eclipse怎么导出可执行jar包

    在eclpse中找到你要导出的java程序 选中它 单击文件 -->export 在弹出的export对话框中找到 jar File 单击选中-->next 按图示顺序依次 选好你的jav ...

  9. python中logging日志基本用法,和进程安全问题

    低配版 import logging logging.debug('debug message') # 调试模式 logging.info('info message') # 正常运转模式 loggi ...

  10. 视图矩阵的推导-opengl应用

    把物体从世界坐标系转化到视点坐标系的矩阵称为视图矩阵. 下面我们先看下opengl视图矩阵的推导过程: 假设视点或camera的局部坐标系为UVN,UVN分别指向右方.上方和后方从而构成右手坐标系,视 ...