Cod sursa(job #2233526)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 23 august 2018 16:01:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <string.h>
using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

const int MOD=100019;

struct item{
                int nr;
                item *nextItem;
           }*Hash[MOD];

void addNumber(int x)
{
    item *pivot=new item;
    int r=x%MOD;
    pivot=Hash[r];
    while(pivot&&pivot->nr!=x) pivot=pivot->nextItem;
    if(pivot==NULL)
    {
        pivot=new item;
        pivot->nr=x;
        pivot->nextItem=Hash[r];
        Hash[r]=pivot;
    }
}

bool checkNumber(int x)
{
    item *pivot=new item;
    int r=x%MOD;
    pivot=Hash[r];
    while(pivot&&pivot->nr!=x) pivot=pivot->nextItem;
    if(pivot) return 1;
    else return 0;
}

int n, sol;

int codeWord(char *word)
{
    int power=1, base=3, code=0;
    n=strlen(word);
    for(int i=0;i<n;++i)
    {
        code=code+(word[i]-'a')*power;
        code%=MOD;
        power=(power*base)%MOD;
    }
    return code;
}

char text[10000001], word[21];

int main()
{
    fin>>text;
    int l=strlen(text);
    while(fin>>word)
    {
        int code=codeWord(word);
        addNumber(code);
    }
    int code=0, power=1, base=3;
    for(int i=0;i<n;++i)
    {
        code=code+(text[i]-'a')*power;
        code%=MOD;
        power=(power*base)%MOD;
    }
    power/=base;
    if(checkNumber(code)) sol++;
    for(int i=n;i<l;++i)
    {
        code=code-(text[i-n]-'a');
        code/=base;
        code=code+(text[i]-'a')*power;
        code%=MOD;;
        if(checkNumber(code)) sol++;
    }
    fout<<sol<<" ";
    return 0;
}