uva10069(DP+大数)
发布时间:2020-12-14 02:26:57 所属栏目:大数据 来源:网络整理
导读:题意:找出B串在A串出现的次数(B在A中可以是不连续的) 解答:设母串的长度是j,子串的长度数i,在假设dp[i][j]:是在长度是j的母串中出现长度是i的子串的个数,如果A[j]!=B[i],dp[i][j]=dp[i][j-1] 如果A[j]==B[i]; dp[i][j]=dp[i-][j-1]+dp[i][j-1]; A[j
题意:找出B串在A串出现的次数(B在A中可以是不连续的) 对于大数直接用JAVA好了 import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String args[]){
int n;
Scanner cin=new Scanner(System.in);
while(cin.hasNext()){
BigInteger dp[][]=new BigInteger[110][10010];
n=cin.nextInt();
String a,b;
while(n-->0){
a=cin.next();
b=cin.next();
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[i].length;j++){
dp[i][j]=BigInteger.ZERO;
}
}
for(int i=0;i<=a.length();i++){
dp[0][i]=BigInteger.ONE;
}
for(int i=1;i<=b.length();i++){
for(int j=i;j<=a.length();j++){
if(b.charAt(i-1)==a.charAt(j-1)){
dp[i][j]=dp[i][j-1].add(dp[i-1][j-1]);
}else {
dp[i][j]=dp[i][j-1];
}
}
}
System.out.println(dp[b.length()][a.length()]);
}
}
}
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
推荐文章
站长推荐
热点阅读