Cod sursa(job #1078029)

Utilizator Athena99Anghel Anca Athena99 Data 11 ianuarie 2014 22:33:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

typedef unsigned int uint;

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

vector <uint> v[mod];

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

    return ch;
}

int 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 uint base3( string ch ) {
    uint 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();
    uint k= base3(c);
    v[k%mod].push_back(k);
    while ( !c.empty() ) {
        c.clear();
        fin>>c;
        if ( c.empty() ) {
            break;
        }
        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]);
    }
    int 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;
}