思路与算法

KMP找出t在s中的所有出现结束位置，同时计算dp[i]表示前i字符的含义选择数。默认沿用dp[i-1]表示当前不选深意；若t在i结束，再加dp[i-|t|]，表示把这一整段作为一个深意词。所有计数模10^9+7。

正确性说明

每种解释由若干互不重叠、取深意的t出现段唯一确定，其他字符取原意。对前i字符，若末端未选择一个t，方案来自dp[i-1]；否则最后段固定为长度|t|的匹配，其前面只能选择前i-|t|的方案。这两类互斥且完整，因此转移正确。KMP允许重叠地发现候选，但DP不会同时选重叠段。

复杂度

每组O(|s|+|t|)时间、O(|s|+|t|)空间，包含前缀函数和dp初始化。最多10组、每串最长10万。每次相加两个模内值小于2×10^9+14，int安全，立即取模。

易错点

所有不取深意的解释也算1种，所以dp[0]=1。不能简单输出2的出现次数次方，因为重叠候选不能同时选。独立答案先用直接find列出区间，再用“跳过/选择并跳到下一不冲突区间”的计数递推。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    const int MOD = 1000000007;
    while (T--) {
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j && t[i] != t[j])
                j = pi[j - 1];
            if (t[i] == t[j])
                ++j;
            pi[i] = j;
        }
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j && s[i] != t[j])
                j = pi[j - 1];
            if (s[i] == t[j])
                ++j;
            dp[i + 1] = dp[i];
            if (j == m) {
                dp[i + 1] = (dp[i + 1] + dp[i + 1 - m]) % MOD;
                j = pi[j - 1];
            }
        }
        cout << dp[n] << '\n';
    }
}