Cod sursa(job #991461)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 30 august 2013 15:42:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<vector>
#define MOD 666013
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
unsigned int n,m,p,i,has,sol;
string s,s1;
vector<unsigned int>v[MOD];
inline void insereaza(string s)
{
    unsigned int has=0;
    for(int i=0;i<s.size();++i)
    has=has*3+s[i]-'a';
    v[has%MOD].push_back(has);
}
inline bool query(unsigned int x)
{
    int key=x%MOD;
    for(unsigned int i=0;i<v[key].size();++i)
    if(v[key][i]==x)
    return 1;
    return 0;
}
int main()
{
    f>>s;
    for(;f>>s1;)
    {
        insereaza(s1);
        m=s1.size();
    }
    n=s.size();
    if(n<m)
    {
        g<<0<<'\n';
        return 0;
    }
    p=1;
    has=0;
    for(i=0;i<m;++i)
    {
        has=s[i]-'a'+has*3;
        if(i!=m-1)
        p=p*3;
    }
    if(query(has))
    ++sol;
    for(i=m;i<n;++i)
    {
        has=has-1LL*p*(s[i-m]-'a');
        has=has*3+s[i]-'a';
        if(query(has))
        ++sol;
    }
    g<<sol<<'\n';
    return 0;
}