【字符串匹配】【后缀数组】17.2.9 T3 最长公共子串 题解

最长公共子串（lcs.in/lcs.out）
给出两个由小写字母组成的字符串s, t，长度分别为n,m ，求它们的最长
公共子串长度。
最长公共子串就是一个最长的字符串，它既是s 也是t 的子串。S 的子串
是指s 中一段连续的字符。
【输入格式】
第一行一个字符串s，表示第一个字符串。
第一行一个字符串t，表示第二个字符串。
【输出格式】
一个整数，最长公共子串长度。
【输入样例】
woshidiyigezifuchuan
woshidiergezifuchuanhahawobidiyigechang
【输出样例】
11
【数据规模】
50% 数据满足 n, m≤1000。
100% 数据满足n, m≤100000。

后缀数组
将两个字符串用#连接后求后缀数组
按height值从大到小将相邻的两个后缀合并
维护合并的块中有无来自不同串的后缀

附AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cctype>
#include <algorithm>
#define clr(x) memset(x,0,sizeof(x))
#define LL long long
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif

using namespace std;

const int Max = 1000010;

struct S{
int wa[Max],wb[Max],wv[Max],ws[Max];
}s;
int rank[Max],height[Max],sa[Max],r[Max];
char str[Max<<1];

inline int cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; }

void d(int *r, int *sa, int n, int m) {         // 
int *x = s.wa, *y = s.wb;
int i,j,p;
for(i = 0; i < m; i++) s.ws[i] = 0;
for(i = 0; i < n; i++) s.ws[x[i] = r[i]]++;
for(i = 1; i < m; i++) s.ws[i] += s.ws[i-1];
for(i = n-1; i >= 0; i--) sa[--s.ws[x[i]]] = i;
for(p = 1, j = 1; p < n; j <<= 1, m = p) {
for(p = 0, i = n-j; i < n; i++) y[p++]=i;
for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;
for(i = 0; i < n; i++) s.wv[i] = x[y[i]];
for(i = 0; i < m; i++) s.ws[i] = 0;
for(i = 0; i < n; i++) s.ws[s.wv[i]]++;
for(i = 1; i < m; i++) s.ws[i] += s.ws[i-1];
for(i = n-1; i >= 0; i--) sa[--s.ws[s.wv[i]]] = y[i];
for(swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i-1], sa[i],j) ? p-1 : p++;
    }
}

void Height(int *r, int *sa, int n) {           //求height 
int j,k = 0;
for(int i = 1; i <= n; i++) rank[sa[i]] = i;
for(int i = 0; i < n; height[rank[i++]] = k)
for(k ? k-- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
}

int main() {
    freopen("lcs.in","r",stdin);
    freopen("lcs.out","w",stdout);
scanf("%s",str);
int len = strlen(str);
int len1 = len;
    str[len] = '#';                             //用'#'连接两个串 
scanf("%s",str+len1+1);
    len = strlen(str);
for(int i = 0; i < len; i++) r[i] = str[i];
    r[len] = 0;
    d(r, sa, len, 300);
    Height(r, sa, len);
int ans = 0;
for(int i = 2; i < len; i++)
if(ans < height[i])
if((sa[i] > len1 && sa[i-1] < len1) || (sa[i] < len1 && sa[i-1] > len1))
                ans = height[i];
printf("%d\n",ans);
return 0;
}