TIOJ 1306 字串中的字串

#include <cstdio>
#include <cstdlib>
#include <string.h>
#define INT64 long long

char s[10005], p[10005];
const INT64 modu = 1e9+7;
INT64 hash[10005];
INT64 modu26[10005];

int main(){
    int T;
    scanf("%d",&T);

    modu26[0] = 1;
    for (int i = 1; i <= 10000; ++i)
        modu26[i] = (modu26[i-1] * 26) % modu;
    
    while(T--){
        scanf("%s",s);
        hash[0] = 0;
        for (int i = 1; i <= strlen(s); ++i)
            hash[i] = (hash[i-1] * 26 + s[i-1] - 'a' + 1) % modu;

        int n;
        scanf("%d",&n);
        while(n--){
            scanf("%s",p);
            int l = strlen(p);
            INT64 p_hash = 0;
            int ans = 0;
            for (int i = 0; i < l; ++i)
                p_hash = (p_hash * 26 + p[i] - 'a' + 1) % modu;

            for (int i = 0; i + l <= strlen(s); ++i){
                INT64 now = (hash[i+l] - hash[i] * modu26[l]) % modu;
                if(now < 0)
                    now += modu;
                if(p_hash == now)
                    ans ++;
            }
            printf("%d\n", ans);
        }
    }
}