hdu5763 Another Meaning KMP+DP

Another Meaning 

先用KMP匹配，将字符串转化为01串。再用个简单的DP

如果当前的串不影响前面的串，那么就可以同时匹配，所以dp[i]=dp[i-1]+dp[i-m]+1，如果当前的串不能匹配，则dp[i]=dp[i-1]，最后输出要输出dp[n-1]+1，因为当所有能匹配的地方都是第一个意思，所以要+1.

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 7, MOD = 1000000007;
char s[N], t[N];
int dp[N], nxt[N];
bool vis[N];
void KMP(char s[], char t[], int n, int m) {
    memset(vis, 0, sizeof vis);
    memset(nxt, -1, sizeof nxt);
    int j = -1, i_r = n - 1;
    for (int i = 1; i < m; ++i) {
        while (j >= 0 && t[j + 1] != t[i])
            j = nxt[j];
        if (t[j + 1] == t[i])
            ++j;
        nxt[i] = j;
    } //getNext
    //for (int i = 0; i < m; ++i) cout << nxt[i] << " "; cout << endl;
    int cnt = 0;
    j = -1;
    for (int i = -1; i < i_r; ++i) {
        while (j >= 0 && t[j + 1] != s[i + 1])
            j = nxt[j];
        if (t[j + 1] == s[i + 1])
            ++j;
        if (j == m - 1) {
            j = nxt[j]; //重叠匹配。j = -1是从头匹配 
            vis[i + 1] = 1;
            //cnt++;
        }
    } //匹配 
    //cout << cnt << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int T, kase = 0;
    cin >> T;
    while (T--) {
        cin >> s >> t;
        memset(dp, 0, sizeof dp);
        int n = strlen(s), m = strlen(t);
        KMP(s, t, n, m);
        for (int i = 0; i <m; ++i)
            dp[i] = vis[i];
        for (int i = m; i < n; ++i) {
            if (vis[i])
                dp[i] = (dp[i - 1] + dp[i - m] + 1) % MOD;
            else dp[i] = dp[i - 1];
        }
        cout << "Case #" << ++kase << ": " << (dp[n - 1] + 1) % MOD << endl;
    }

    return 0;
}