本来看到两个最长公共子串,我就直接掏\(O({n^2})\)算法了……比如这个……
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace HIHOCODER_WEEK122
{
class Program
{
static void Main(string[] args)
{
string str1 = Console.ReadLine();
string str2 = Console.ReadLine();
LCS lcs = new LCS(str1, str2);
Console.WriteLine(lcs.Length);
}
}
class LCS
{
public int Length { get; private set; }
public LCS(string str1,string str2)
{
Length = 0;
int lStr1 = str1.Length;
int lStr2 = str2.Length;
if (lStr1 == 0 || lStr2 == 0)
{
Length = 0;
return;
}
int[,] table = new int[lStr1, lStr2];
int longest = 0;
for (int i = 0; i < lStr2; ++i)
table[0, i] = (str1[0] == str2[i] ? 1 : 0);
for (int i = 1; i < lStr1; ++i)
{
table[i, 0] = (str1[i] == str2[0] ? 1 : 0);
for (int j = 1; j < lStr2; ++j)
{
if (str1[i] == str2[j])
{
table[i, j] = table[i - 1, j - 1] + 1;
}
}
}
for (int i = 0; i < lStr1; ++i)
{
for (int j = 0; j < lStr2; ++j)
{
if (longest < table[i, j])
{
longest = table[i, j];
}
}
}
Length = longest;
}
}
}
然后我就TLE了……
我想不对啊,然后一看……
要用后缀数组……
求完height之后判断一下,SA[i]和SA[i-1]是不是分别在两个串里。
//code source:http://www.xuebuyuan.com/2116000.html
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 420000;
int s[maxn], rs[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], Rank[maxn], height[maxn];
int n, m, k, tt, l1, l2;
char s1[maxn], s2[maxn];
#define min(x,y) x>y?y:x
#define max(x,y) x<y?y:x
inline int idx(char s)
{
return s - 'a' + 2;
}
void getheight(int n)
{
int i, k = 0;
for (i = 0; i <= n; i++) Rank[sa[i]] = i;
for (i = 0; i < n; i++)
{
if (k) k--;
int j = sa[Rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
}
void build_ss(int m, int n)
{
n++;
int i, *x = t, *y = t2;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (i = n - k; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++;
if (p >= n) break;
m = p;
}
}
bool diff(int x, int y)
{
int a = min(x, y);
int b = max(x, y);
if (a<l1 && b>l1) return true;
return false;
}
int main()
{
cin >> s1;
cin >> s2;
l1 = strlen(s1);
l2 = strlen(s2);
for (int i = 0; i < l1; i++)
s[i] = idx(s1[i]);
s[l1] = 0;
n = l1 + 1;
for (int i = 0; i < l2; i++)
{
s[n++] = idx(s2[i]);
}
s[n] = 1;
build_ss(128, n);
getheight(n);
int ans = 0;
for (int i = 2; i < n; i++)
{
if (diff(sa[i], sa[i - 1]))
ans = max(ans, height[i]);
}
cout << ans;
return 0;
}