Long Long Message POJ - 2774(最长公共子串)
2024-08-26 21:27:39
题意:
给你两串字符,要你找出在这两串字符中都出现过的最长子串
解析:
先用个分隔符将两个字符串连接起来,再用后缀数组求出height数组的值,找出一个height值最大并且i与i-1的sa值分别在两串字符中就好了
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
int ran[maxn], height[maxn]; void get_sa(int m)
{
int i, *x = t, *y = t2;
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[i] = s[i]]++;
for(i = ; i < m; i++) c[i] += c[i-];
for(i = n-; i >= ; i--) sa[--c[x[i]]] = i;
for(int k = ; k <= n; k <<= )
{
int p = ;
for(i = n-k; i < n; i++) y[p++] = i;
for(i = ; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[y[i]]]++;
for(i = ; i< m; i++) c[i] += c[i-];
for(i = n-; i >= ; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = ; x[sa[]] = ;
for(i = ; i < n; i++)
x[sa[i]] = y[sa[i-]] == y[sa[i]] && y[sa[i-]+k] == y[sa[i]+k] ? p- : p++;
if(p >= n) break;
m = p;
}
int k = ;
for(i = ; i < n; i++) ran[sa[i]] = i;
for(i = ; i < n; i++)
{
if(k) k--;
int j = sa[ran[i]-];
while(s[i+k] == s[j+k]) k++;
height[ran[i]] = k;
}
} char s1[maxn], s2[maxn];
int main()
{
while(~scanf("%s%s", s1, s2)){
n = ;
int len1 = strlen(s1);
rep(i, , len1)
s[n++] = s1[i] - 'a' + ; s[n++] = ;
int len2 = strlen(s2);
rep(i, , len2)
s[n++] = s2[i] - 'a' + ;
s[n++] = ;
get_sa();
int maxx = -INF;
rep(i, , n)
{
if(height[i] > maxx && sa[i] < len1 && sa[i-] > len1 && sa[i] >= )
maxx = height[i];
else if(height[i] > maxx && sa[i-] < len1 && sa[i] > len1 && sa[i-] >= )
maxx = height[i];
}
cout<< maxx <<endl;
} return ;
}
最新文章
- Site Not Found
- 油田 Oil Deposits
- linux 修改端口限制
- JS判断checkbox至少选择一项
- JLINK仿真器与ST-LINK仿真器的安装与配置.pdf
- NET的可运行于树莓派
- (转)ManyToMany注解
- 使用redis所维护的代理池抓取微信文章
- docker容器安装及使用技巧
- javascript 特殊的面向对象以及继承详解(入门篇)
- Android Studio安装Genymotion插件
- 我的python渗透测试工具箱之自制netcat
- 想玩 Android 开发板?这些常用命令你不知不行!
- EnableEurekaServer基本配置
- Java 并发编程-再谈 AbstractQueuedSynchronizer 2:共享模式与基于 Condition 的等待 / 通知机制实现
- CentOS 7从Python 2.7升级至Python3.6.1
- onkeyup+onafterpaste 只能输入数字和小数点--转载
- C#中连接MySQL数据
- 转载:(Mac)在bash和zsh配置环境变量path的几种方法
- matlab stereo_gui立体标定