Cod sursa(job #1481489)

Utilizator mirupetPetcan Miruna mirupet Data 4 septembrie 2015 17:31:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream>
#include<vector>
#include<string>
#define MOD 1000003
#define MAX 50005
using namespace std;

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

unsigned int nr, i, a, SOL;
unsigned int v[250], w[23];
string S, T;
vector < unsigned int > Hash[MOD + 3];

inline bool Search(unsigned int);

int main()
    {
        w[1] = 1;
        for (i = 2; i <= 20; i++)
            w[i] = w[i - 1] * 3;

        v['a'] = 0, v['b'] = 1, v['c'] = 2;

        f >> S;
        while (f >> T)
        {
            nr = T.size();

            a = 0;
            for (i = 0; i < nr; i++)
                a += w[i + 1] * v[T[i]];
            Hash[a % MOD].push_back(a);
        }

        a = 0;
        for (i = 0; i < nr; i++)
            a += w[i + 1] * v[S[i]];

        SOL = Search(a);
        for (i = nr; i < S.size(); i++)
        {
            a /= 3;
            a += w[nr] * v[S[i]];
            SOL += Search(a);
        }

        g << SOL << '\n';
    }

inline bool Search(unsigned int Val)
{
    vector <unsigned int> :: iterator it;
    int line = Val % MOD;

    for (it = Hash[line].begin(); it != Hash[line].end(); it++)
          if (*it == Val)
            return 1;
    return 0;
}