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

BelowLuminous edited 3 年前

在这里提一下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,还是算了吧

Comments

kblack

你也在网上刷题啊

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

正解是SA+LCP,推荐EOJ1805

欢迎访问我的主页!http://godweiyang.com
#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;
}
你当前正在回复 博客/题目
存在问题!