Cod sursa(job #2291556)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 28 noiembrie 2018 11:15:22
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <vector>
#include<string.h>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int M=1<<15;
vector <int> H[M];
int cautare(int x){
    int p=x%M;
    int i;
    for(i=0;i<(int)H[p].size();i++)
        if(H[p][i]==x)
    return 1;
    return 0;
}
void inserare(int x){
    int p=x%M;
    H[p].push_back(x);
}
int main()
{
    char s[10000002],c[22];
    int l1,l2,i,h,p,rez;
    f>>(s+1);
    l1=strlen(s+1);
    while(f>>(c+1))
    {
        l2=strlen(c+1);
        h=0;
        for(i=1;i<=l2;i++)
            h=h*3+c[i]-'a';
        inserare(h);
    }
    p=1;
    for(i=1;i<=l2;i++)
        p*=3;
    for(i=1;i<=l2;i++)
        h=h*3+s[i]-'a';
    rez=0;
    if(cautare(h))
        rez++;
    for(i=l2+1;i<=l1;i++)
    {
        h*=3;
        h-=(s[i-l2]-'a')*p;
        h+=s[i]-'a';
        if(cautare(h))
           rez++;
    }
    g<<rez;
    return 0;
}