Cod sursa(job #1501056)

Utilizator akaprosAna Kapros akapros Data 12 octombrie 2015 22:58:26
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxN 10000002
#define maxL 22
#define mod 6613
#define b 3
#define ui unsigned int
using namespace std;
int sol, n, j, l, nr;
ui code, codes;
char s[maxN], a[maxL];
vector < ui > V[mod];
int ok(int x, ui p)
{
    int i;
    for (i = 0; i < V[x].size(); ++ i)
        if (V[x][i] == p)
            return 1;
    return 0;
}
void read()
{
    int nr = 0, i;
    freopen("abc2.in", "r", stdin);
    gets(s);
    while (1)
    {
        ++ nr;
        a[0] = 'd';
        gets(a);
        code = 0;
        if (a[0] == 'd')
        {
            -- nr;
            return ;
        }
        if (nr == 1)
            l = strlen(a);
        for (i = 0; i < l; ++ i)
            code = (code * b + a[i] - 'a');
        V[code % mod].push_back(code);
    }
}
void solve()
{
    ui pbl = 1;
    int i;
    for (i = 1; i <= l; ++ i)
        pbl = pbl * b;
    n = strlen(s);
    for (i = 0; i < n; ++ i)
    {
        codes = codes * b + s[i] - 'a';
        if (i >= l - 1)
        {
            if (i - l >= 0)
                codes = codes - (pbl * (s[i - l] - 'a'));
            if (codes < 0)
                codes += mod;
            if (ok(codes % mod, codes))
                ++ sol;
        }
    }
}
void write()
{
    freopen("abc2.out", "w", stdout);
    printf("%d\n", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}