hdu6153

201708 （ACM）字符串----KMP

• 之前做的一道AC自动机和这个很像
  
  • 整理一下之前这道题的思路：
  • 给出n个串，求有哪几个前缀在当前t串（t串是n个串之一）中出现过，需要$O(n)$实现。
  • 首先t串自己的前缀肯定在t串中出现过，考虑某个前缀x=t[1...i]，那么x的失败指针指向的节点y的含义是t[j...i]。所以如果从x开始一直沿着失败指针向上，表示的点是所有t[j...i];
• 这道题两个串倒置一下，题意变成：求t串每个前缀在s串中出现的次数。
  
  • ns[i]表示s[0...i]的后缀最长能匹配多长t串的前缀。假设能匹配的长度是t[0...j]，那么沿着nt[j]向前跳一次，表示s[i-k...i]与t[0...k]匹配。所以如果一直沿着nt数组向前跳，表示的点是所有s[j..i]。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
#define dd(a) cout<<#a<<"="<<a<<" ";
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=1000005;
const int mod=1e9+7;
int ns[N],nt[N];
char s[N],t[N];   
void kmp(char *s,int *ns,char *t,int *nt){
    int lens = strlen(s);
    int lent = strlen(t);
    nt[0] = -1;
    for(int i=0,j=-1;i<lens;++i){
        while(j >= 0 && s[i] != t[j + 1]) j = nt[j];
        if(s[i] == t[j + 1]) ++j;
        ns[i] = j;
        if(j + 1 == lent) j = nt[j];
    }
}
void KMP(){
    scanf("%s%s",s,t);
    reverse(s,s+strlen(s));
    reverse(t,t+strlen(t));
    kmp(t+1,nt+1,t,nt);
    kmp(s,ns,t,nt);
}
ll cnt[N];
void solve() {
    for(int i=0;s[i];++i) {
        if(~ns[i]) ++cnt[ns[i]];
    }
    ll ans=0;
    for(int i=strlen(t)-1;~i;--i) {
        ans=(ans+1ll*(i+1)*cnt[i]%mod)%mod;
        cnt[nt[i]]=(cnt[nt[i]]+cnt[i])%mod;
    }
    printf("%lld\n",ans);
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        memset(cnt,0,sizeof(cnt));
        KMP();
        solve();
    }
    return 0;
}