// [解题方法]
// dp[i][j]表示Z串的[0~i]子串在X串的[0~(j-1)]子串中的出现次数
// 初始化:dp[i][0] = 0
// 状态转移1:
// dp[0][j+1] = (Z[0]==X[j])?(dp[0][j]+1):(dp[0][j])
// 状态转移2(i>0):
// dp[i][j+1] = (Z[i]==X[j])?(dp[i][j]+dp[i-1][j]):(dp[i][j])
// 这题需要大数运算,我偷懒用了java
// 另外由于每次转移实际上只用到两个数组,所以这里就只开了两个数组循环使用,相当于滚动数组了
import java.util.*;
import java.io.*;
import java.math.*;
public class Main
{
static public void main (String[] args) throws IOException
{
Scanner cin = new Scanner (new BufferedInputStream (System.in));
BigInteger dp[][] = new BigInteger [2][10001];
int t, n, m, i, j, k;
String s, p;
t = cin.nextInt();
while (t > 0)
{
t--;
s = cin.next();
p = cin.next();
n = s.length();
m = p.length();
k = 0;
dp[0][0] = dp[1][0] = BigInteger.valueOf(0);
for (j = 0; j < n; j++)
{
dp[k][j+1] = dp[k][j];
if (s.charAt(j) == p.charAt(0))
dp[k][j+1] = dp[k][j+1].add(BigInteger.valueOf(1));
}
for (i = 1; i < m; i++)
{
k = (k+1)%2;
for (j = 0; j < n; j++)
{
dp[k][j+1] = dp[k][j];
if (s.charAt(j) == p.charAt(i))
dp[k][j+1] = dp[k][j+1].add(dp[(k+1)%2][j]);
}
}
System.out.println(dp[k][n]);
}
}
}
分享到:
相关推荐
Distinct Subsequences烟雨迷楼1
Distinct Subsequences字符串距离
115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】
不同的子序列 给定两个字符串s和t,返回等于t的s的不同子序列数。 字符串的子序列是通过删除某些字符(可以是无字符)而不会干扰其余字符的相对位置而从原始字符串形成的新字符串。 (即,“ ACE”是“ ABCDE”的子...
1.三角形找一条从顶到底的最小路径 2.最大子数组和 3.回文最小划分次数 4.最佳时间买卖股票 5. 判断字符串s3是否由s1,s2交叉存取组成 ...9. 不同的子序列Distinct Subsequences 10.单词分解Word Break
MySQL通常使用GROUPBY(本质上是排序动作)完成DISTINCT操作,如果DISTINCT操作和ORDERBY操作组合使用,通常会用到临时表.这样会影响性能. 在一些情况下,MySQL可以使用索引优化DISTINCT操作,但需要活学活用.本文涉及一个...
有这样的一个需求:select count(distinct nick) from user_access_xx_xx; 这条sql用于统计用户访问的uv,由于单表的数据量在10G以上,即使在user_access_xx_xx上加上nick的索引, 通过查看执行计划,也为全索引扫描...
完美解决distinct中使用多个字段的方法,完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法
Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...
mysql中distinct用法【SQL中distinct的用法】.docx
oracle rownum和distinct
EFCore查询不重复数据Distinct,根据两个字段排序
主要介绍了MongoDB教程之聚合,MongoDB除了基本的查询功能之外,还提供了强大的聚合功能,这里主要介绍count、distinct和group,需要的朋友可以参考下
使用Distinct查询.rar使用Distinct查询.rar
distinct的使用.docx
【DISTINCT】优化之MySQL官方文档翻译
如果我想知道颜值有哪些取值,所以希望从结果集中去掉重复的记录,加上distinct关键字,位置在select和字段列表之间。distinct是从结果集中筛选出唯
用Distinct在MySQL中查询多条不重复记录值,绝对的物有所值
leetcode 分类 LeetCode Progress 128/154 Other Solutions ...Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar