Cod sursa(job #1368535)

Utilizator japjappedulapPotra Vlad japjappedulap Data 2 martie 2015 18:23:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int MOD = 99991;

char Main[10000001], C[22];
unsigned int N, Sol, MainSize;
unsigned int P3[22], X;

vector <unsigned int> Hash[MOD];

inline void Insert(unsigned int value);
inline int Find(unsigned int value);

int main()
{
    P3[0] = 1;
    for (int i = 1; i <= 21; ++i)
        P3[i] = P3[i-1] * 3;
    is >> Main;
    while (is >> C)
    {
        N = strlen(C);
        X = 0;
        for (int i = 0; i < N; ++i)
            X += (P3[i]) * (C[i] - 'a');
        Insert(X);
    }
    N = strlen(C);
    MainSize = strlen(Main);
    X = 0;
    for (int i = 0; i < N; ++i)
        X += (P3[i]) * (Main[i] - 'a');

    Sol += Find(X);

    for (int i = N; i < MainSize; ++i)
    {
        X /= 3;
        X += P3[N-1] * (Main[i] - 'a');
        Sol += Find(X);
    }

    Sol += Find(X);

    os << Sol;

    is.close();
    os.close();
}

inline int Find(unsigned int value)
{
    unsigned int R = value % MOD;
    unsigned int aux;
    for (auto it = Hash[R].begin(); it != Hash[R].end(); ++it)
        if ( *it == value)
            return 1;
    return 0;
};

inline void Insert(unsigned int value)
{
    unsigned int R = value % MOD;
    for (auto& it : Hash[R])
        if (it == value)
            return;
    Hash[R].push_back(value);
};




















/*

bbcabbabcba
11201101210

*/