http://codevs.cn/problem/3160/

sam的裸题。。。(之前写了spoj上另一题sam的题目,但是spoj被卡评测现在还没评测完QAQ打算写那题题解时再来详细介绍sam的。。。。那就再等等吧。

求两个串的lcs话,就是先建立a串的sam,然后用b的字串去匹配a中。

因为sam中的转移可以直接对应所有后缀的开头,因此匹配的时候是可以直接找到这个后缀开头,然后继续转移,直至找到整个串。而因为sam中的parent指针就如ac自动机中的fail指针差不多,唯一的区别是sam的parent指针转移到的节点是自己的后缀(就是S到当前节点就是一个原串的前缀,而上面说的就是这个前缀的后缀,而且长度每次都递减,因此能找到最大匹配)

所以不断找然后更新即可。

如果还不懂详看clj论文

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } struct sam {
static const int N=200005;
int c[N][26], l[N], f[N], root, last, cnt;
sam() { cnt=0; root=last=++cnt; }
void add(int x) {
int now=last, a=++cnt; last=a;
l[a]=l[now]+1;
for(; now && !c[now][x]; now=f[now]) c[now][x]=a;
if(!now) { f[a]=root; return; }
int q=c[now][x];
if(l[q]==l[now]+1) { f[a]=q; return; }
int b=++cnt;
memcpy(c[b], c[q], sizeof c[q]);
l[b]=l[now]+1;
f[b]=f[q];
f[q]=f[a]=b;
for(; now && c[now][x]==q; now=f[now]) c[now][x]=b;
}
void build(char *s) {
int len=strlen(s);
rep(i, len) add(s[i]-'a');
}
int find(char *s) {
int ret=0, len=strlen(s), now=1, t=0;
rep(i, len) {
int x=s[i]-'a';
if(c[now][x]) now=c[now][x], ++t;
else {
while(now && !c[now][x]) now=f[now];
if(!now) now=root, t=0;
else t=l[now]+1, now=c[now][x];
}
ret=max(ret, t);
}
return ret;
}
}a;
const int N=100005;
char s[N];
int main() {
scanf("%s", s);
a.build(s);
scanf("%s", s);
printf("%d\n", a.find(s));
return 0;
}

  


题目描述 Description

给出两个由小写字母组成的字符串,求它们的最长公共子串的长度。

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入 Sample Input
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother
样例输出 Sample Output

27

数据范围及提示 Data Size & Hint

单个字符串的长度不超过100000

最新文章

  1. Python正则表达式中的re.S
  2. Dual Number
  3. java jps 命令详解
  4. python为什么会有@classmethod?
  5. 使用shadow dom封装web组件
  6. 《java作业》
  7. do break的妙用
  8. ios开发--编码格式
  9. InfluxDB安装
  10. CentOS 6.7增加SWAP交换分区
  11. [Java] LinkedList / Queue - 源代码学习笔记
  12. Chrome开发者工具详解(3):Timeline面板
  13. 写代码质量改善java计划151建议——导航开始
  14. hdu 1002 Java 大数 加法
  15. Linux中oops信息调试【转】
  16. 【CJOJ2498】【DP合集】最长上升子序列 LIS
  17. codeforces 842C Ilya And The Tree
  18. 【算法】BILSTM+CRF中的条件随机场
  19. 解决IOS移动端固定定位失效问题
  20. Maven+SpringMVC+SpringFox+Swagger整合示例

热门文章

  1. java注解,通过反射解析注解,模仿hibernate,获取sql语句。
  2. Spring 切面优先级
  3. ubuntu 设置计划任务
  4. git——分布式版本控制系统
  5. 【laravel5.4】DB::table的操作
  6. LibRec:一个实现推荐系统的Java库包
  7. spring Log4j关于No appenders could be found for logger的警告
  8. 用lambda表达式树替代反射
  9. c#+mysql 中文乱码
  10. HttpPutFormContentFilter 和 ContextLoaderListener 讲解