Cod sursa(job #1816532)

Utilizator silkMarin Dragos silk Data 26 noiembrie 2016 16:33:48
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define NMax 10000005
#define TMax 25
using namespace std;

const int P = 474707;
const int Q = 147481;

char s[NMax+1];
char w[TMax+1];
vector<int> h[P];
int a,b,ans;

inline void add()
{
    h[a].push_back(b);
}

bool is()
{
    for(int i = 0; i < h[a].size(); ++i)
    if( h[a][i] == b ) return 1;
return 0;
}

int main(){
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);

    int i,N,T,pwrP,pwrQ;

    fgets(s,NMax,stdin);
    N = strlen(s)-1;
    for(i = 0; i < N; ++i) s[i] = s[i] - 'a';

    while( fgets(w,TMax,stdin) && !feof(stdin) )
    {
        a = b = 0;
        T = strlen(w);
        if( w[T-1]=='\n' ) --T;

        for(i = 0; i < T; ++i)
        {
            a = ( a * 3 + w[i] - 'a' ) % P;
            b = ( b * 3 + w[i] - 'a' ) % Q;
        }
        add();
    }

    for(a = b = i = 0; i < T; ++i)
    {
        a = ( a * 3 + s[i] ) % P;
        b = ( b * 3 + s[i] ) % Q;
    }

    if( is() ) ++ans;

    for(pwrP = pwrQ = i = 1; i < T; ++i)
    {
        pwrP = ( pwrP * 3 ) % P;
        pwrQ = ( pwrQ * 3 ) % Q;
    }

    for(i = T; i < N; ++i)
    {
        a = ( ( ( a - pwrP * s[i-T] ) % P + P ) * 3 + s[i] ) % P;
        b = ( ( ( b - pwrQ * s[i-T] ) % Q + Q ) * 3 + s[i] ) % Q;
        if( is() ) ++ans;
    }

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



return 0;
}