Cod sursa(job #2296919)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 5 decembrie 2018 08:43:36
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda prega_casi_5.12.2018 Marime 1.21 kb
#include <fstream>
	
#include<vector>
	
#include<cstring>
	
#define prim 30031
	
using namespace std;
	
 
	
ifstream cin("abc2.in");
	
ofstream cout("abc2.out");
	
 
	
char text[10000002], word[21];
	
vector<unsigned int> Hash[prim];
	
unsigned int pow3[21], cod, key, dim, n,m, match = 0, i, j;
	
 
	
 
	
int main()
	
{
	
    pow3[0] = 1;
	
    for( i = 1; i<=21; ++i) pow3[i] = pow3[i-1]*3;
	
 
	
    cin>>text;
	
    m = strlen(text);
	
 
	
    while(cin>>(word))
	
    {
	
        n = strlen(word);
	
        cod = 0;
	
        for(i = 0; i<n; ++i) cod += (word[i] - 'a')*pow3[i];
	
        Hash[cod%prim].push_back(cod);
	
    }
	
    cod = 0;
	
 
	
    for( i = 0; i<n; ++i){
	
        cod+=(text[i] - 'a')*pow3[i];
	
    }
	
    for(; i<m; ++i){
	
        key = cod%prim;
	
        dim = Hash[key].size();
	
        for( j = 0; j<dim; ++j){
	
            if(Hash[key][j]==cod){
	
            match++;
	
            break;
	
            }
	
        }
	
        cod/=3;
	
        cod+=pow3[n-1]*(text[i]-'a');
	
    }
	
    key = cod%prim;
	
    dim = Hash[key].size();
	
    for(i = 0; i<dim; ++i){
	
        if(Hash[key][i]==cod){
	
        match++;
	
        break;
	
        }
	
    }
	
 
	
    cout<<match;
	
 
	
    return 0;
	
}