AcWing 3713. 不同的子序列
原题链接
中等
作者:
卡冈图亚
,
2023-07-16 03:30:31
,
所有人可见
,
阅读 133
降维+预处理 时间复杂度$O(Tnm/26)$
常规求子序列的方法显然不能满足时间和空间复杂度要求
结合状态转移方程改变枚举顺序可优化一维空间
同时观察到只有s[i] == t[j]时状态才会转移,可预处理26个字母在t中的位置,注意逆序
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ri register int
#define endl '\n'
#define rep(i, x, y) for(ri i = x; i <= y; ++ i)
#define pre(i, x, y) for(ri i = x; i >= y; -- i)
#define x first
#define y second
#define lowbit(x) (x&(-x))
#define maxe max_element
#define mine min_element
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
using namespace std;
using i64 = int64_t;
const int N = 1e4 + 10, mod = 1000000007;
int T, n, m;
vector<int> pos[30];
string s, t;
int f[N];
int main()
{
IOS;
cin >> T;
while(T --)
{
rep(i, 0, 25) pos[i].clear();
cin >> s >> t;
n = s.length();
m = t.length();
s = " " + s;
t = " " + t;
pre(i, m, 1)
{
ri k = t[i] - 'a';
pos[k].push_back(i);
}
memset(f, 0, sizeof f);
f[0] = 1;
rep(i, 1, n)
{
ri k = s[i] - 'a';
for(auto j:pos[k]) f[j] = (f[j] + f[j - 1]) % mod;
}
cout << f[m] << endl;
}
return 0;
}