Cod sursa(job #798095)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 15 octombrie 2012 18:56:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#include<string.h>
#include<vector>

using namespace std;

#define MAXL 10000005
#define MOD 666013
#define MAXP 25

vector < long long int > v[ MOD ];
long long int POW[ MAXP ];
long long int aux;
int n, m, i, p, b = 3, res;
char S[ MAXL ], P[ MAXP ];

inline int search_value(long long int val)
{
    int l;
    vector < long long int > :: iterator ii;

    l = val % MOD;

    for(ii = v[l].begin(); ii != v[l].end(); ++ii)
        if(*ii == val)
            return 1;

    return 0;
}

inline void insert_value(long long int val)
{
    int l;
    vector < long long int > :: iterator ii;

    l = val % MOD;

    v[l].push_back(val);
}

int main()
{

    POW[0] = 1;
    for(i = 1; i <= 22; ++i)
        POW[i] = b * POW[i-1];

    FILE *f = fopen("abc2.in", "r");

    fgets(S, 10000002, f);
    n = strlen(S) - 2;

    fgets(P, 22, f);
    m = strlen(P) - 2;

    while(!feof(f))
    {
        if(strlen(P) - 2 == m)
        {
            aux = 0;
            for(i = 0; i <= m; ++i)
                aux = aux * b + (P[i] - 'a');
            if(!search_value(aux))
                insert_value(aux);
        }
        fgets(P, 22, f);
    }

    fclose(f);

    aux = 0;
    for(i = 0; i <= m; ++i)
        aux = aux * b + (S[i] - 'a');

    res += search_value(aux);

     for(i = m + 1; i <= n; ++i)
     {
        aux = (aux - (S[i-m-1] - 'a') * POW[m]) * b + S[i] - 'a';
        res += search_value(aux);
     }


    FILE *g = fopen("abc2.out", "w");

    fprintf(g, "%d\n", res);

    fclose(g);

    return 0;
}