子序列

時(shí)間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：4 描述

給定兩個(gè)字符串序列A,B，求A序列不同位置構(gòu)成的子序列中和B序列相同的有多少個(gè)。

例如A序列為a₁b₂c₃d₄c₅(序列為abcc,12345是為區(qū)分位置而加入的數(shù)字)，B序列abc

這A序列不同位置構(gòu)成的子序列中和B相同的有a₁b₂c_3，a₁b₂c_5兩個(gè)

?

輸入

第一行一個(gè)數(shù)N（N不大于5）表示有N組測試數(shù)據(jù)
以下每組測試數(shù)據(jù)有兩行 分別是字符串A和B，其中A串的長度不大于100000，B串的長度不多于1000，并且B長度多于100的只有一組數(shù)據(jù)

輸出

對(duì)應(yīng)每組數(shù)據(jù)輸出一個(gè)整數(shù)，由于數(shù)字可能會(huì)很大，請(qǐng)對(duì)10003取余后再輸出

樣例輸入

3 a aa abcbc abc abcdefabcdefdefa a

樣例輸出

0 3 3

AC碼：

#include<stdio.h> #include<string.h> char ch1[100005],ch2[1005]; int f[1005]; int main() {int T,len1,len2,i,j;scanf("%d",&T);while(T--){scanf("%s%s",ch1,ch2);len1=strlen(ch1);len2=strlen(ch2);memset(f,0,sizeof(f));if(len1<=len2){if(strcmp(ch1,ch2)==0)printf("1\n");elseprintf("0\n");}else{f[0]=1;for(i=0;ch1[i]!='\0';i++){for(j=len2-1;j>=0;j--){if(j<=i&&ch1[i]==ch2[j])f[j+1]=(f[j]+f[j+1])%10003;}}printf("%d\n",f[len2]);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 336 子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。