Cod sursa(job #1462891)

Utilizator felixiPuscasu Felix felixi Data 19 iulie 2015 13:19:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>

using namespace std;

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

const int NMAX = 50000;
const int MOD  = 666013;

struct DAP {
    int v,c;
};

string s;
string c;
vector <int> H[MOD+1];
int L;
int Ans = 0;

int FORMULA( string str ) {
    int p = 1, k = 0;
    for( int i = (int)str.size()-1;  i >= 0;  --i, p*= 3 ) {
        k += p * (int)( str[i] - 'a' );
    }
    return k;
}

void Push_hash( int val ) {
    int key = val % MOD;
    H[key].push_back( val );
}

void Check_hash( int val ) {
    int key = val % MOD;
    for( int i = 0;  i < (int)H[key].size();  ++i ) {
        if( H[key][i] == val ) {
            ++Ans;
            break;
        }
    }
}

int main() {
    in >> s;
    while( in >> c ) {
        L = (int)c.size();
        int aux = FORMULA(c);
        Push_hash( aux );
    }

    long long k = 0, p = 1;
    for( int i = L-1;  i >= 0;  --i ) {
        k += p * (int)( s[i] - 'a' );
        p *= 3;
    }
    Check_hash( k );
    p /= 3;

    for( int i = L;  i < (int)s.size();  ++i ) {
        k -= (int)( s[i-L] - 'a' ) * p;
        k = k*3 + (int)( s[i] - 'a' );
        Check_hash( k );
    }

    out << Ans << '\n';
    return 0;
}