Cod sursa(job #594862)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 10 iunie 2011 00:42:46
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char l[10000010],ch[30];
unsigned int v[50001];

int main()
{
    unsigned int m,n,q,i,j,aux,step,sol=0,x=0;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    l[0]=' ';
    fgets(l+1,10000005,stdin);
    n=strlen(l)-2;
    fgets(ch,25,stdin);
    m=strlen(ch)-1;
    for (i=0;i<m;++i)
        v[1]=v[1]*3+ch[i]-'a';
    i=1;
    while (!feof(stdin))
    {
        ++i;
        fgets(ch,25,stdin);
        for (j=0;j<m;++j)
            v[i]=v[i]*3+ch[j]-'a';
    }
    q=i;
    sort(v+1,v+q+1);
    for (aux=1,i=1;i<m;++i)
    {
        aux*=3;
        x=x*3+l[i]-'a';
    }
    for (j=1;j<=n-m+1;++j)
    {
        x=(x-(x/aux)*aux)*3+l[j+m-1]-'a';
        for (step=1;step<q;step<<=1);
        for (i=1;step;step>>=1)
            if (i+step<=q&&v[i+step]<=x)
                i+=step;
        if (v[i]==x)
            ++sol;
    }
    printf("%u\n",sol);
    return 0;
}