Cod sursa(job #1078021)

Utilizator Athena99Anghel Anca Athena99 Data 11 ianuarie 2014 22:17:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

typedef long long i64;

const int pow= 20;
const int mod= 6613;

vector <i64> v[mod];

int check( int x ) {
    int ch= 0;
    for ( vector <i64>::iterator it= v[x%mod].begin(); it!=v[x%mod].end(); ++it ) {
        if ( *it==x ) {
            ch= 1;
            break;
        }
    }

    return ch;
}

i64 t[pow];
string s, c;

inline int charint( char ch ) {
    int sol= 0;
    if ( ch=='b' ) {
        sol= 1;
    } else if ( ch=='c' ) {
        sol= 2;
    }
    return sol;
}

inline i64 base3( string ch ) {
    i64 sol= 0;
    for ( int i= 0; i<(int)ch.size(); ++i ) {
        sol= sol*3+charint(ch[i]);
    }

    return sol;
}

int main(  ) {
    t[0]= 1;
    for ( int i= 1; i<pow; ++i ) {
        t[i]= t[i-1]*3;
    }
    
    fin>>s>>c;
    int n= (int)s.size(), m= (int)c.size();
    i64 k= base3(c);
    v[k%mod].push_back(k);
    while ( !c.empty() ) {
        c.clear();
        fin>>c;
        k= base3(c);
        if ( !check(k) ) {
            v[k%mod].push_back(k);
        }
    }

    k= 0;
    for ( int i= 0; i<m; ++i ) {
        k= k*3+charint(s[i]);
    }
    i64 sol= 0;
    if ( check(k) ) {
        ++sol;
    }
    for ( int i= m; i<n; ++i ) {
        k= (k-t[m-1]*charint(s[i-m]))*3+charint(s[i]);
        if ( check(k) ) {
            ++sol;
        }
    }
    fout<<sol<<"\n";

    return 0;
}