TIOJ 1306 . 字串中的字串

http://tioj.ck.tp.edu.tw/problems/1306

重點:
* %在把P放到暫存區時有點慢 ==> const + if

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

typedef long long int int64;

const int64 P = 1000000007, X = 31;

int64 Xn[10010];

void init(){

    Xn[0] = 1;

    for(int lx = 1;lx <= 10001;lx++){

        Xn[lx] = Xn[lx-1]*X;

        Xn[lx] %= P;

    }

    return;

}

struct hasher{

    int64 val[10010];

    int len;

    hasher(char* _str){

        val[0] = 0;

        len = strlen(_str);

        for(int lx = 0; _str[lx] != 0;lx++){

            val[lx+1] = val[lx]*X + (int64)(_str[lx] - 'a');

            val[lx+1] %= P;

        }

        return;

    }

    int64 getval(int a, int b){

        int64 ret = val[b] - val[a-1]*Xn[b-a+1];

        ret %= P; if(ret < 0) ret += P;

        return ret;

    }

};

int64 hash(char* _str){

    int64 ret = 0;

    for(int lx = 0;_str[lx] != 0;lx++){

        ret = ret*X + (int64)(_str[lx] - 'a');

        ret %= P;

    }

    return ret;

}

int main(){

    init();

    char mstr[10010], istr[10010];

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

    while(T--){

        scanf("%s", mstr);

        hasher hash_mstr(mstr);

        int Q; scanf("%d", &Q);

        while(Q--){

            scanf("%s", istr);

            int len = strlen(istr);

            int c = 0;

            int cpval = hash(istr);

            for(int lx = 1;lx + len-1 <= hash_mstr.len;lx++){

                c += hash_mstr.getval(lx, len + lx-1) == cpval;

            }

            printf("%d\n", c);

        }

    }

    return 0;

}