Codeforces 163A Substring and Subsequence 题解

发表于 | 更新于 | 阅读次数：
本文字数： 560 字 | 阅读时长 ≈ 2 分钟

震惊！一sb少年被一个A题卡了半天！

题意简述

给定两个字符串$a,b$，求有多少对有序对$(x,y)$使得$x$是$a$的子串，$y$是$b$的子序列。两字符串长度$<=5000$，空间$5000\times 5000\times 5$是够的。

思路框架

裸的$DP$。

具体思路

$dp[i][j]$表示考虑$a$的前$i$位，$b$的前$j$位的答案。那么，$dp[i][j]$=$dp[i-1][k]$的和$+1$，其中$k\in [1,j-1]$，并且$a[i]==b[j]$。

这个转移式很好理解。就是在$ai$和$bj$相同的时候，两种情况

  1. 上一个位置的答案，就是前面的求和
  2. $a[i]$和$b[j]$取出来，也是一种方案。

但是，这个转移是$O(n^3)$的，那咋整嘛。

我们会发现，这个转移式珂以用前缀和优化。

设$sum[i][j]$表示$dp[i][1…j]$的和。然后$dp[i][j]=sum[i-1][j-1]+1$。

每次求完$dp$之后，维护一下$sum$。

时空复杂度最高$O(n^2)$。其中$n=5000$。稳过。

（相信CF的机子）

代码

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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 5003
    #define mod 1000000007 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    char a[N],b[N];
    int la,lb;
    void Input()
    {
        scanf("%s%s",a+1,b+1);
        la=strlen(a+1),lb=strlen(b+1);
    }

    int dp[N][N];
    int sum[N][N];
    void Soviet()
    {
        if (a[1]==b[1]) dp[1][1]=1;
        F(i,2,lb) if (a[1]==b[i]) dp[1][i]=1;
        F(i,2,la) if (a[i]==b[1]) dp[i][1]=1;
        F(i,1,lb) sum[1][i]=sum[1][i-1]+dp[1][i];
        F(i,2,la)
        {
            F(j,2,lb)
            {
                if (a[i]==b[j])
                {
                    dp[i][j]=sum[i-1][j-1]+1;
                }
                else dp[i][j]=0;
                dp[i][j]%=mod;
            }
            F(j,1,lb) sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
        }

        int ans=0;
        F(i,1,la) ans=(ans+sum[i][lb])%mod;
        printf("%d\n",ans%mod);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w