// [解题方法]
// 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字符串距离
java java_leetcode题解之Distinct Subsequences.java
《Distinct Subsequences:C++实现解析》 在编程竞赛或算法设计中,"Distinct Subsequences" 是一个常见的问题,它涉及到动态规划(Dynamic Programming)这一重要概念。这道题目要求我们找出一个主串(字符串S)中...
115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】
python python_leetcode题解之115_Distinct_Subsequences
javascript js_leetcode题解之115-distinct-subsequences.js
不同的子序列 给定两个字符串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操作,但需要活学活用.本文涉及一个...
MySQL 中 DISTINCT 用法详解 MySQL 中的 DISTINCT 关键字用于返回唯一不同的值,避免重复值的出现。当我们在查询表中数据时,可能会遇到重复值的情况,这时使用 DISTINCT 关键字可以帮助我们返回唯一的值。 ...
在MySQL数据库中,优化`DISTINCT`操作是一个关键的性能提升策略,特别是在处理大量数据时。上述场景中,用户遇到了一个问题:对一个10G以上的单表`user_access_xx_xx`执行`SELECT COUNT(DISTINCT nick)`以统计唯一...
完美解决distinct中使用多个字段的方法,完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法
在SQL语言中,`DISTINCT`关键字是一种非常重要的查询方式,它用于消除查询结果中的重复行,从而确保返回的数据是唯一的。本教程将深入探讨如何使用`DISTINCT`查询,以及在不同场景下它的应用。 一、DISTINCT基本...
在SQL语言中,`DISTINCT`关键字是一个非常重要的部分,特别是在数据检索时,它帮助我们去除结果集中的重复行,确保返回的每一行都是唯一的。本文将深入探讨`DISTINCT`在Oracle数据库中的使用,以及如何与其他SQL元素...
`Distinct()`方法是C# LINQ中用于去除重复元素的关键操作,而在EFCore中,它可以应用于数据库查询来过滤掉重复记录。 首先,让我们深入理解`Distinct()`方法。在C#中,`Distinct()`方法通过比较元素的默认等价关系...
"Oracle 中的 ROWNUM 和 DISTINCT" Oracle 中的 ROWNUM 和 DISTINCT 是两个非常重要的关键词,它们在查询数据时发挥着至关重要的作用。然而,许多开发者在使用这两个关键词时,却常常会遇到一些不太理解的地方,...
Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...
### DISTINCT优化之MySQL官方文档翻译解析 #### 一、引言 在数据库查询操作中,经常需要使用`DISTINCT`关键字来去除重复记录,确保结果集中的每一条记录都是唯一的。然而,在某些场景下,使用`DISTINCT`可能会导致...
在本教程中,我们将深入探讨MongoDB中的三个关键聚合操作:`count`、`distinct`和`group`。 1. `count` 函数: `count` 方法用于计算集合中符合特定条件的文档数量。在MongoDB中,你可以直接调用`db.collection....