UOJ Logo Sharp Sword 剑锋 OI

SSOI

#63. string(string.pas/cpp/c)

统计

【问题描述】

    小A非常开心,但在开心之余她还想考考小 K。小A定义L为X与Y的最长公共子序列的长度(子序列在字符串内不一定连续,一个长度为L的字符串有 2L个子序列,包括空子序列)。现在小 A取出了X的所有长度为L的子序列,并要求小K回答在这些子序列中,有多少个是 Y 的子序列。
    因为答案可能很大,所以小K只需要回答最终答案模 10^9 + 7。

【输入格式】

第一行包含一个非空字符串 X。
第二行包含一个非空字符串 Y。
字符串由小写英文字母构成。

【输出格式】

对于每组测试数据输出一个整数,表示对应的答案。

【输入样例1】

aa
ab

【输出样例1】

2

【时空限制】

2S
512MB

【子任务】

对于 20%的数据,1 ≤ |X|,|Y| ≤ 10; 对于 100%的数据,1 ≤ |X|,|Y| ≤ 1000。