http://acm.hdu.edu.cn/showproblem.php?pid=6153
首先相当于翻转两个串，然后求s2前缀在s1中出现的次数。
这是一个套路啦
首先把两个串结合起来，中间加一个'%'之类的分割
设dp[i]表示前缀1---i在本串中的出现次数和
那么从后开始dp，所有dp值一开始都是1，表示前缀出现了一次，就是自己本身。
转移，设当前去到第i位，则dp[next[i + 1] - 1] += dp[i]
就是ABACABA这样，已经知道了ABACABA出现了一次，然后前后缀ABA和ABA重复出现，那么dp[3]肯定能够加上dp[7]的，dp[7]包含了dp[7]个"ABA"，就这个意思。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 2e6 + ;
int nextliu[maxn], dp[maxn];
char str[maxn], sub[maxn];
void get_next (char str[], int nextliu[], int lenstr) {
int i = , j = ;
nextliu[] = ;
while (i <= lenstr) {
if (j == || str[i] == str[j]) {
nextliu[++i] = ++j;
} else j = nextliu[j];
}
return ; }
const int MOD = 1e9 + ;
int dp2[maxn];
void work() {
scanf("%s%s", str + , sub + );
int lenstr = strlen(str + ), lensub = strlen(sub + );
reverse(str + , str + + lenstr);
reverse(sub + , sub + + lensub);
int to = lensub + ;
sub[to++] = '$';
for (int i = ; i <= lenstr; ++i) sub[to++] = str[i];
sub[to] = '\0';
to--;
for (int i = ; i <= lensub; ++i) dp[i] = ;
for (int i = lensub + ; i <= to; ++i) dp[i] = ;
get_next(sub, nextliu, to);
for (int i = to; i >= ; --i) {
int t = nextliu[i + ] - ;
dp[t] += dp[i];
dp[t] %= MOD;
}
// printf("%d\n", dp[2] - dp2[2]);
LL ans = ;
for (int i = ; i <= lensub; ++i) {
ans += 1LL * i * dp[i] % MOD;
ans %= MOD;
}
printf("%I64d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
其实也可以用后缀数组 + dp搞，不过TLE了，应该要用DC3，不去搞了