Cod sursa(job #798079)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 15 octombrie 2012 18:14:58
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 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 t[ MAXL ];
long long int aux;
int n, m, i, p, b = 4, 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);
}

long long int POW(int a, int b)
{
    long long int res = 1;

    while(b)
        res = (long long) res * a, --b;
    return res;
}

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

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

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

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

     for(i = m + 1; i <= n; ++i)
        t[i] = (t[i-1] - (S[i-m-1] - 'a' + 1) * POW(b, m)) * POW(b, m-2) + S[i] - 'a' + 1;

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

    fclose(f);

    for(i = m; i <= n; ++i)
        if(search_value(t[i]))
            ++res;

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

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

    fclose(g);

    return 0;
}