Cod sursa(job #1501041)

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