LCS的一些应用

发表于 分类于 阅读次数： 评论数：
本文字数： 645 阅读时长 ≈ 2 分钟
本文记录了LCS(最长公共子序列)的一些应用

喜闻乐见的 $n^2$ 算法:

不妨设 $dp[i][j]$ 表示第一个串 $s$ 的前 $i$ 位，第二个串 $t$ 的前 $j$ 位的 $LCS$ 的长度，那么状态转移方程是：

1
2
3
4
5
6
7
8
9
10
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&s[i]);
for(int i=1;i<=m;i++)scanf("%d",&t[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
 	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    if(s[i]==t[j])
 	    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
cout<<dp[n][m];

$n \ logn$的算法

因为可以转化为最长递增子序列问题，所以这样复杂度是可行的。

洛谷全排列LCS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
memset(f, 0x3f, sizeof f);
f[0] = 0;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i] , pos[a[i]] = i;
for(int i = 1; i <= n; i++) cin >> b[i];
int mx = 0;
for(int i = 1; i <= n; i++){
    if(pos[b[i]] > f[mx]) f[++mx] = pos[b[i]];
    else{
        int l = 0, r = mx, mid;
        while(l < r){
            mid = (l+r) >> 1;
            if(f[mid] > pos[b[i]]) r = mid;
            else l = mid + 1;
        }
        f[l] = min(f[l], pos[b[i]]);
    }
}
cout << mx << endl;

算法可行性的证明：
样例：
s : 3 2 1 4 5 => a b c d e
t : 1 2 3 4 5 => c b a d e
如此，只要求出 $t$ 中的 $LIS$ 即可。

nlogn求LCS问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int maxn =250*250;
const int inf=1000000000;
int s[maxn],g[maxn],d[maxn];
int num[maxn];//num[x]为整数x的新编号，num[x]=0表示x没有在A中出现过、
int N,p,q,x;
int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&N,&p,&q);
        memset(num,0,sizeof(num));
        for(int i=1;i<=p+1;i++)
        {
            scanf("%d",&x);
            num[x]=i;
        }
        int n=0;
        for(int i=0;i<q+1;i++)
        {
            scanf("%d",&x);
            if(num[x])
                s[n++]=num[x];
        }
        //求解s[0]...s[n-1]的LIS
        for(int i=1;i<=n;i++)
           g[i]=inf;
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int k=lower_bound(g+1,g+n+1,s[i])-g;//在g[1]~g[n]中查找
            d[i]=k;
            g[k]=s[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",++tt,ans);
    }
    return 0;
}

如果给的序列不是全排列也问题不大。

对于序列A{},B{},我们可以记录下来B中的每个元素在A中出现的位置，按顺序保存在一个新序列当中，
如果有多个位置按倒序写，没有就不用写，然后对这个新序列求一个LIS就是两个序列的LCS长度。
证明算法可行性：
考虑，对于A序列，下标编号记为1—-n1，B和A的最长公共子序列在A中对应的编号肯定是递增的，

所以B中的这些元素对应的A的编号也是递增的，为了重复计算当有多个编号时倒序存入，表示只能选一个，尽管有多个编号但在B中这只是一个元素。

例子：
A={3,9,7,10,3} B={5,3,7,3}
列出B对应的A中的编号(1—5)
5:无
3:1,5
7:3
3:1,5

参考博客
nlogn求可重复最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define maxn 100000+10
using namespace std;
int a[maxn],dp[maxn];
vector<int>location[26];
char s1[maxn],s2[maxn];
void init(){
    for(int i=0;i<=maxn;++i)
        a[i]=dp[i]=0;
}
void LCS(){
    init();
    int i,j,k,w,ans,l,r,mid;
    int lena=strlen(s1),lenb=strlen(s2);
    for(i=0;i<26;i++)location[i].clear();
    for(i=lenb-1;i>=0;--i)location[s2[i]-'a'].push_back(i);
    for(i=0,k=0;s1[i];i++)
        for(j=0;j<location[w=s1[i]-'a'].size();++j,++k)
            a[k]=location[w][j];
    dp[1]=a[0];
    dp[0]=-1;
    for(i=ans=1;i<k;++i){
        l=0;r=ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(dp[mid]>=a[i])r=mid-1;
            else l=mid+1;
        }
        if(r==ans)
            ans++,dp[r+1]=a[i];
        else if(dp[r+1]>a[i])dp[r+1]=a[i];
    }
    cout<<ans<<endl;
}
int main(){
    while(scanf("%s%s",s1,s2)!=EOF)LCS();
    return 0;
}

基于位运算的最长公共子序列

这个是零几年时候ioi集训队的题目。

研究报告

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// from claris
#include <cstdio>
typedef long long ll;
const int BIT = 808, E = 62;
int n1, n2, m, h, i, j, p, ans;
char s[50000], t[50000];
struct Num {
    ll x[BIT];
    Num() {
        for (int i = 0; i < BIT; i++) x[i] = 0;
    }
    void set(int p) { x[p / E] |= 1LL << (p % E); }
    Num operator&(Num b) {
        Num c;
        for (int i = 0; i <= m; i++) c.x[i] = x[i] & b.x[i];
        return c;
    }
    Num operator|(Num b) {
        Num c;
        for (int i = 0; i <= m; i++) c.x[i] = x[i] | b.x[i];
        return c;
    }
    Num operator^(Num b) {
        Num c;
        for (int i = 0; i <= m; i++) c.x[i] = x[i] ^ b.x[i];
        return c;
    }
    Num operator-(Num b) {
        Num c;
        for (int i = 0; i <= m; i++) c.x[i] = x[i] - b.x[i];
        for (int i = 0; i < m; i++)
            if (c.x[i] < 0) c.x[i] += (1LL << E), c.x[i + 1]--;
        return c;
    }
    void shl() {
        ll o = 1, p;
        for (int i = 0; i <= m; o = p, i++) {
            p = x[i] & (1LL << h), (x[i] <<= 1) &= ~(1LL << (h + 1));
            if (o) x[i] |= 1;
        }
    }
} ap[4], x, row[2];
int hash(int x) {
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    return 3;
}
int main() {
    scanf("%d %d %s %s", &n1, &n2, s, t);
    i = 0;
    for (m = (n1 - 1) / E, h = (m ? E : n1) - 1; i < n1; i++)
        ap[hash(s[i])].set(i);
    for (i = 0; i < n2; i++) {
        p ^= 1;
        x = ap[hash(t[i])] | row[p ^ 1];
        row[p ^ 1].shl();
        row[p] = x & ((x - row[p ^ 1]) ^ x);
    }
    for (i = m; ~i; i--)
        for (j = h; ~j; j--)
            if (row[p].x[i] & (1LL << j)) ans++;
    printf("%d", ans);
}

一些题目

-------------本文结束感谢您的阅读-------------