Cod sursa(job #1795039)

Utilizator Gigel-FroneGigel Fronel Gigel-Frone Data 1 noiembrie 2016 22:08:41
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define mod 666013
#define base 3

using namespace std;

char text[1000001], word[50001];
vector <unsigned int> list[mod+1];

vector <unsigned int> :: iterator find_value(unsigned int value)
{
    unsigned int k=value % mod;
    vector <unsigned int> :: iterator it;
    for(it=list[k].begin(); it<list[k].end(); it++)
        if(*it == value) return it;
    return list[k].end();
}

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

    gets(text);
    unsigned int length_of_text=strlen(text), length_of_word, ans=0;
    unsigned int power[22];

    power[0]=1;
    for(int i=1; i<=20; i++) power[i]=power[i-1]*base;

    unsigned int x=0;
    while(gets(word))
    {
        length_of_word=strlen(word);
        x=0;
        for(int i=0; i<length_of_word; i++) x+=power[i]*(word[i]-'a');
        list[x%mod].push_back(x);
    }
    x=0;
    for(int i=0; i<length_of_word; i++) x+=power[i]*(text[i]-'a');
    if(find_value(x) != list[x%mod].end()) ans++;

    for(int i=length_of_word; i<length_of_text; i++)
    {
        x/=base;
        x+=power[length_of_word-1]*(text[i]-'a');
        if(find_value(x) != list[x%mod].end()) ans++;
    }
    printf("%d", ans);
}