Cod sursa(job #1588001)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 2 februarie 2016 18:38:17
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef unsigned int ui;

const int Mn = 1e7 + 8;
const int mod = 6613;

int n,m,sol;
ui val,pw[21];
char s[Mn],w[21];
vector< ui > h[mod];

bool found(ui x)
{
    ui y = x % mod;

    for (int i = 0;i < h[y].size();i++)
        if (h[y][i] == x)
           return 1;

    return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);

     scanf("%s",s);
     n = strlen(s);
     pw[0] = 1;

     for (int i = 1;i <= 20;i++)
         pw[i] = pw[i - 1] * 3;

     for (;!feof(stdin);)
     {
         scanf("%s",w);
         m = strlen(w);
         val = 0;

         for (int i = 0;i < m;i++)
             val = val + pw[i] * (w[i] - 'a');

         if (!found(val))
            h[val % mod].push_back(val);
     }

     val = 0;
     for (int i = 0;i < m;i++)
         val = val + pw[i] * (s[i] - 'a');

     sol = found(val);
     for (int i = m;i < n;i++)
     {
         val = val / 3 + pw[m - 1] * (s[i] - 'a');
         sol += found(val);
     }

     printf("%d\n",sol);

  return 0;
}