`

UVA 10069 Distinct Subsequences

阅读更多
//  [解题方法]
//  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]);
		}
	}
}
1
2
分享到:
评论

相关推荐

    Distinct Subsequences

    Distinct Subsequences字符串距离

    java-leetcode题解之Distinct Subsequences.java

    java java_leetcode题解之Distinct Subsequences.java

    Distinct Subsequences烟雨迷楼1

    《Distinct Subsequences:C++实现解析》 在编程竞赛或算法设计中,"Distinct Subsequences" 是一个常见的问题,它涉及到动态规划(Dynamic Programming)这一重要概念。这道题目要求我们找出一个主串(字符串S)中...

    115.Distinct Subsequences不同的子序列【LeetCode单题讲解系列】

    115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】

    python-leetcode题解之115-Distinct-Subsequences

    python python_leetcode题解之115_Distinct_Subsequences

    js-leetcode题解之115-distinct-subsequences.js

    javascript js_leetcode题解之115-distinct-subsequences.js

    Distinct-Subsequences-

    不同的子序列 给定两个字符串s和t,返回等于t的s的不同子序列数。 字符串的子序列是通过删除某些字符(可以是无字符)而不会干扰其余字符的相对位置而从原始字符串形成的新字符串。 (即,“ ACE”是“ ABCDE”的子...

    常见动态规划问题总结

    1.三角形找一条从顶到底的最小路径 2.最大子数组和 3.回文最小划分次数 4.最佳时间买卖股票 5. 判断字符串s3是否由s1,s2交叉存取组成 ...9. 不同的子序列Distinct Subsequences 10.单词分解Word Break

    MySQL中索引优化distinct语句及distinct的多字段操作

    MySQL通常使用GROUPBY(本质上是排序动作)完成DISTINCT操作,如果DISTINCT操作和ORDERBY操作组合使用,通常会用到临时表.这样会影响性能. 在一些情况下,MySQL可以使用索引优化DISTINCT操作,但需要活学活用.本文涉及一个...

    mysql中distinct用法【SQL中distinct的用法】.docx

    MySQL 中 DISTINCT 用法详解 MySQL 中的 DISTINCT 关键字用于返回唯一不同的值,避免重复值的出现。当我们在查询表中数据时,可能会遇到重复值的情况,这时使用 DISTINCT 关键字可以帮助我们返回唯一的值。 ...

    分析MySQL中优化distinct的技巧

    在MySQL数据库中,优化`DISTINCT`操作是一个关键的性能提升策略,特别是在处理大量数据时。上述场景中,用户遇到了一个问题:对一个10G以上的单表`user_access_xx_xx`执行`SELECT COUNT(DISTINCT nick)`以统计唯一...

    完美解决distinct中使用多个字段的方法

    完美解决distinct中使用多个字段的方法,完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法完美解决distinct中使用多个字段的方法

    使用Distinct查询.rar

    在SQL语言中,`DISTINCT`关键字是一种非常重要的查询方式,它用于消除查询结果中的重复行,从而确保返回的数据是唯一的。本教程将深入探讨如何使用`DISTINCT`查询,以及在不同场景下它的应用。 一、DISTINCT基本...

    distinct的使用.docx

    在SQL语言中,`DISTINCT`关键字是一个非常重要的部分,特别是在数据检索时,它帮助我们去除结果集中的重复行,确保返回的每一行都是唯一的。本文将深入探讨`DISTINCT`在Oracle数据库中的使用,以及如何与其他SQL元素...

    EFCore查询不重复数据Distinct.docx

    `Distinct()`方法是C# LINQ中用于去除重复元素的关键操作,而在EFCore中,它可以应用于数据库查询来过滤掉重复记录。 首先,让我们深入理解`Distinct()`方法。在C#中,`Distinct()`方法通过比较元素的默认等价关系...

    oracle rownum和distinct

    "Oracle 中的 ROWNUM 和 DISTINCT" Oracle 中的 ROWNUM 和 DISTINCT 是两个非常重要的关键词,它们在查询数据时发挥着至关重要的作用。然而,许多开发者在使用这两个关键词时,却常常会遇到一些不太理解的地方,...

    javalruleetcode-learn-algorithms::laptop:Java实现的各种算法题解

    Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...

    【DISTINCT】优化之MySQL官方文档翻译

    ### DISTINCT优化之MySQL官方文档翻译解析 #### 一、引言 在数据库查询操作中,经常需要使用`DISTINCT`关键字来去除重复记录,确保结果集中的每一条记录都是唯一的。然而,在某些场景下,使用`DISTINCT`可能会导致...

    MongoDB教程之聚合(count、distinct和group)

    在本教程中,我们将深入探讨MongoDB中的三个关键聚合操作:`count`、`distinct`和`group`。 1. `count` 函数: `count` 方法用于计算集合中符合特定条件的文档数量。在MongoDB中,你可以直接调用`db.collection....

Global site tag (gtag.js) - Google Analytics