分享一个理论上是NlogN时间复杂度的LCS(最长公共子串)算法

BelowLuminous edited 6 年，7 月前

在这里提一下O(n log n)的算法

假设有两个序列 s1[ 1~6 ] = { a, b, c , a, d, c }, s2[ 1~7 ] = { c, a, b, e, d, a, b }。

记录s1中每个元素在s2中出现的位置, 再将位置按降序排列, 则上面的例子可表示为：

loc( a）= { 6, 2 }, loc( b ) = { 7, 3 }, loc( c ) = { 1 }, loc( d ) = { 5 }。

将s1中每个元素的位置按s1中元素的顺序排列成一个序列s3 = { 6, 2, 7, 3, 1, 6, 2, 5, 1 }。

在对s3求LIS得到的值即为求LCS的答案。

这个方法理论复杂度为O(n log n)（即求LIS n log n），但是在遇到极端情况时会退化：

假设字符串s1=“000”，s2=“0000”，则序列s3={4,3,2,1,4,3,2,1,4,3,2,1}，求LIS的最终时间复杂度为O(nm log(nm) )，不如O(nm)的算法。

如果字符串s1=“0101”，s2=“1010”，（0,1个数相等）则序列s3={4,2,3,1,4,2,3,1}，求LIS的最终时间复杂度为O(nm/2 log(nm/2))，只要nm>4，复杂度就不如O(nm)的算法。

所以说面对01字符串LCS，O(n log n)的算法毫无意义。

且不说这个，O(nm)的算法还能把空间强行优化到O(m)，O(n log n)的算法的空间复杂度为O(s3的长度)，极限情况下为O(nm)，还不能优化，，，

假如说。。数据范围是s1,s2长度<=8000，时限3s，那么面对极限数据s1=s2=”000..”(8000个0)时，O(n^m)显然常数很小，应该能卡过去，但显然O(n log n)算法，，，MLE+TLE，还是算了吧

kblack

6 年，7 月前

你也在网上刷题啊

回复 1 0

欢迎访问我的主页!http://godweiyang.com

6 年，7 月前

正解是SA+LCP，推荐EOJ1805

回复 0 0

欢迎访问我的主页!http://godweiyang.com

6 年，7 月前

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <climits>
#include <new>
#include <utility>
#include <iterator>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

const int maxn = 1000200;

int n, k;
int sa[maxn], Rank[maxn], tmp[maxn], lcp[maxn];

bool compare_sa(int i, int j)
{
    if (Rank[i] != Rank[j])
        return Rank[i] < Rank[j];
    int ri = i + k <= n ? Rank[i+k] : -1;
    int rj = j + k <= n ? Rank[j+k] : -1;
    return ri < rj;
}

void construct_sa(char* s)
{
    n = strlen(s);
    for (int i = 0; i <= n; ++i)
    {
        sa[i] = i;
        Rank[i] = i < n ? s[i] : -1;
    }
    for (k = 1; k <= n; k <<= 1)
    {
        sort(sa, sa+n+1, compare_sa);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; ++i)
            tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
        for (int i = 0; i <= n; ++i)
            Rank[i] = tmp[i];
    }
}

void construct_lcp(char* s)
{
    n = strlen(s);
    for (int i = 0; i <= n; ++i)
        Rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int j = sa[Rank[i]-1];
        if (h > 0)
            h--;
        for (; j + h < n && i + h < n; ++h)
            if (s[j+h] != s[i+h])
                break;
        lcp[Rank[i]-1] = h;
    }
}

void solve()
{
    char s[200000], t[100000];
    scanf("%s%s", s, t);
    int len = strlen(s);
    s[len] = ' ';
    for (int i = len+1; i <= len*2; ++i)
        s[i] = t[i-len-1];
    s[len*2+1] = 0;
    construct_sa(s);
    construct_lcp(s);
    int ans = 0;
    for (int i = 0; i < strlen(s); ++i)
        if ((sa[i] < len) != (sa[i+1] < len))
            ans = max(ans, lcp[i]);
    printf("%d\n", ans);
}

int main()
{
    solve();
    return 0;
}

回复 0 0

分享一个理论上是NlogN时间复杂度的LCS(最长公共子串)算法

Comments

服务

开源

关于我们