题解：P16104 [ICPC 2019 NAIPC] Subsequences in Substrings

ybc_7653_bo · 2026-07-23 15:06:23 · 题解

看到题解大多是 O(n^2) 的时间复杂度，在极端数据下容易时间超限，于是来一篇 DP 的题解。

题目大意

给定字符串 s 和 t，求出 s 中有多少个字串包含 t 作为子序列。

解题思路

如果枚举所有的字串，然后判断是否是子序列，那么时间复杂度就是 O(n^2m)，直接爆炸，于是我们想怎么优化。
这里通过模拟样例发现，如果在 l 到 r 满足了条件，那么以 1 到 l 作为左端点的区间也是可以的。
所以我们固定右端点，找到最靠右的左端点，那么就可以快速求得其他的了。
定义 f_j 为扫描到当前位置时，匹配完 t 的前 j 个字符后，最靠右的起始位置。
那么初始化就是 f_0=i：还没有匹配，最靠右的就是右端点。
转移方程是如果 f_{j-1}\ne-1，并且 s_j=t_j，那么 f_j=\max(f_j,f_{j-1})。因为如果已经能从位置 f_j 的位置开始匹配，且当 s_j=t_j，那么 t_{1\dots j} 就能从位置 f_{j-1} 开始匹配。

代码实现

#include<bits/stdc++.h>
#define int long long     //需要开long long 
#define MAX 0x3f3f3f3f3f3f3f3f
#define MIN -0x3f3f3f3f3f3f3f3f
#define endl "\n"
using namespace std;
string s , t;
int n , m , ans , f [ 110 ];
signed main()
{
    ios_base :: sync_with_stdio ( 0 );
    cin . tie ( nullptr );
    cout . tie ( nullptr );
    cin >> s >> t;
    n = s . size ();
    m = t . size ();
    s = ' ' + s;
    t = ' ' + t;
    memset ( f , -1 , sizeof ( f ) );    //初始化 
    for ( int i = 1 ; i <= n ; i++ )
    {
        f [ 0 ] = i;     //赋初值 
        for ( int j = m ; j >= 1 ; j-- )      //倒叙枚举，类似01背包滚动数组优化，如果正序枚举，那么会导致同一个值被使用多次 
        {
            if ( f [ j - 1 ] != -1 && s [ i ] == t [ j ] )
            {
                f [ j ] = max ( f [ j ] , f [ j - 1 ] );     //转移 
            }
        }
        if ( f [ m ] != -1 )
        {
            ans += f [ m ];     //累计答案 
        }
    }
    cout << ans;
    return 0;
}

最后看了一下，没想到竟然是最优解，果然 DP 的潜力是无限的。