题解【poj2774 Long Long Message】
2024-09-02 01:30:55
Description
求两个串的最长连续公共字串
Solution
后缀数组入门题吧
把两个串连在一起,中间加一个分隔符,然后跑一遍后缀数组,得到 height 和 sa
一个 height[i] 对答案有贡献的充要条件是 sa[i] 和 sa[i-1] 分别在两个串中
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 200200;
char s1[N], s2[N], S[N];
int n, tmpn, cnt[N], ans, sa[N], rk[N], height[N];
struct node { int id, x, y; } a[N], b[N];
int main() {
scanf("%s %s", s1, s2); tmpn = strlen(s1);
for(int i = 0; s1[i]; i++) S[++n] = s1[i]; S[++n] = '#';
for(int i = 0; s2[i]; i++) S[++n] = s2[i];
for(int i = 1; i <= n; i++) cnt[S[i]] = 1;
for(int i = 0; i <= 128; i++) cnt[i] += cnt[i - 1];
for(int i = 1; i <= n; i++) rk[i] = cnt[S[i]];
for(int L = 1; L <= n; L *= 2) {
for(int i = 1; i <= n; i++)
a[i].id = i, a[i].x = rk[i], a[i].y = rk[i + L];
for(int i = 1; i <= n; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[a[i].y]++;
for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
for(int i = 1; i <= n; i++) b[cnt[a[i].y]--] = a[i];
for(int i = 1; i <= n; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[a[i].x]++;
for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
for(int i = n; i >= 1; i--) a[cnt[b[i].x]--] = b[i];
for(int i = 1; i <= n; i++)
if(a[i].x == a[i - 1].x && a[i].y == a[i - 1].y)
rk[a[i].id] = rk[a[i - 1].id];
else rk[a[i].id] = rk[a[i - 1].id] + 1;
} for(int i = 1; i <= n; i++) sa[rk[i]] = i;
int k = 0;
for(int i = 1; i <= n; i++) {
int j = sa[rk[i] - 1]; if(k) k--;
while(i + k <= n && j + k <= n && S[i + k] == S[j + k]) k++;
height[rk[i]] = k;
} for(int i = 1; i <= n; i++)
if(sa[i] <= tmpn && sa[i - 1] > tmpn ||
sa[i] > tmpn && sa[i - 1] <= tmpn)
ans = max(ans, height[i]);
printf("%d\n", ans);
return 0;
}
最新文章
- 使用Notepad++实现批量将ANSI转成为UTF-8编码
- EmptyRecycle() 清空回收站
- nodejs安装和环境搭建
- 任务调度quartz
- JSTL之迭代标签库
- Ubuntu下MySql配置
- 深入理解C#:编程技巧总结(一)
- IAAS云计算产品畅想-云主机产品内涵
- java程序员入门:英语好不好对编程到底有没有影响
- jstack
- JAVA课程设计---学生基本信息管理系统(201521123039 王兴)
- 太嚣张了!他竟用Python绕过了“验证码”
- git更新Activemq在远程github上指定版本的源码步骤
- 【C/C++】C++11 Lambda
- 文本建模、文本分类相关开源项目推荐(Pytorch实现)
- MySQL索引优化看这篇文章就够了!
- 【Luogu3602】Koishi Loves Segments(贪心)
- 3、zabbix配置入门
- 在Azure DevOps Server(TFS系统)中部署回退/回滚方案(Rollback)
- 【RS】Improving Implicit Recommender Systems with View Data - 使用浏览数据提升隐式推荐系统