Cod sursa(job #1984861)

Utilizator victoreVictor Popa victore Data 26 mai 2017 12:37:17
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstdio>
#include<vector>
#include<cstring>
#define mod 666013
#define key(a) (a%666013)
#define un unsigned

using namespace std;

const un int nmax=1e7+5;

vector<int>g[mod+1];
int n,nsec;
char sir[nmax],pattern[25];

inline un int val(char ch)
{
    return ch-'a';
}
inline void add_num(un int x)
{
    int k=key(x);
    g[k].push_back(x);
}
inline bool find_num(un int x)
{
    int k=key(x);
    vector<int>::iterator it;
    for(it=g[k].begin();it!=g[k].end();++it)
        if(*it==x)
            return 1;
    return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    un int n,i,rez=0,number;
    gets(sir+1);
    n=strlen(sir+1);
    gets(pattern+1);
    nsec=strlen(pattern+1);
    number=0;
    for(i=1;i<=nsec;i++)
        number=number*3+val(pattern[i]);
    add_num(number);
    for(;gets(pattern+1);)
    {
        number=0;
        for(i=1;i<=nsec;i++)
            number=number*3+val(pattern[i]);
        add_num(number);
    }
    number=0;
    un int putere=1;
    for(i=1;i<=nsec;i++)
    {
        number=number*3+val(sir[i]);
        putere*=3;
    }
    putere/=3;
    rez+=find_num(number);
    for(i=nsec+1;i<=n;i++)
    {
        number-=putere*val(sir[i-nsec]);
        number=number*3+val(sir[i]);
        rez+=find_num(number);
    }
    printf("%d",rez);
}