Cod sursa(job #1490788)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 24 septembrie 2015 09:59:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <bitset>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#define nmax 50005
#define lmax 10000005
#define kmax 22
#define mod1 200005
#define mod2 1000023
using namespace std;

int n,m,mc,sol,t1,t2,h1,h2;
char s[lmax],a[kmax];
char buffer[lmax/5];


vector<long long> v[mod1];

void hashins(int t1,int t2)
{
    v[t1].push_back(t2);
}
int hashexist(int t1,int t2)
{
    for (int i=0;i<v[t1].size();i++)
        if (v[t1][i]==t2)
            return 1;
    return 0;
}
int main()
{
    int i,j;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);

    scanf("%s",&s);
    n=strlen(s);

    while (scanf("%s",&a)==1) {
        m=strlen(a);
        if (m) mc=m;
        t1=0;t2=0;
        for (i=0;a[i];i++) {
            t1=(1LL*t1*3+a[i]-'a')%mod1;
            t2=(1LL*t2*3+a[i]-'a')%mod2;
        }
        hashins(t1,t2);
    }
    m=mc;
    t1=0;t2=0;h1=1;h2=1;
    for (i=0;i<m;i++) {
        t1=(1LL*t1*3+s[i]-'a')%mod1;
        t2=(1LL*t2*3+s[i]-'a')%mod2;
    }
    for (i=1;i<m;i++) {
        h1=(1LL*h1*3)%mod1;
        h2=(1LL*h2*3)%mod2;
    }
    for (i=m;i<=n;i++) {
        if (hashexist(t1,t2))
            sol++;
        t1=(1LL*t1-h1*(s[i-m]-'a')+2*mod1);
        t2=(1LL*t2-h2*(s[i-m]-'a')+2*mod2);

        t1=((1LL*t1*3+s[i]-'a')+2*mod1)%mod1;
        t2=((1LL*t2*3+s[i]-'a')+2*mod2)%mod2;

        }
    printf("%d\n",sol);

    return 0;
}