Cod sursa(job #1984740)

Utilizator victoreVictor Popa victore Data 25 mai 2017 20:33:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
//BAZA 3
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int mod1=666013;
const int mod2=363277;
const int nmax=10000005;

bool viz[666013];
char c[nmax],pattern[25];
int sp[nmax];

inline short int num(char ch)
{
    return ch-'a';
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    int n,i,j,putere=1,nr=0,cmp=0,cmp2=0,nr2=0,putere2,numerus,cnt=0,med,st,dr;
    bool ok=0;
    char cu;
    gets(c+1);
    numerus=strlen(c+1);
    gets(pattern+1);
    n=strlen(pattern+1);
    for(i=1;i<=n;i++)
    {
        nr=(nr*3+num(c[i]))%mod1;
        cmp=(cmp*3+num(pattern[i]))%mod1;
        if(i!=1)
            {
                putere=putere*3%mod1;
            }
    }
    sp[1]=nr;
    if(sp[1]==cmp)
    {
        cnt++;
        viz[cmp]++;
    }
    for(i=n+1;i<=numerus;i++)
    {
        sp[i-n+1]=(((sp[i-n]-(num(c[i-n])*putere)%mod1+mod1)%mod1)*3 + num(c[i]))%mod1;
        if(sp[i-n+1]==cmp)
        {
            cnt++;
            viz[cmp]=1;
        }
    }
    sort(sp+1,sp+numerus+1-n);
    while(scanf("%c",&cu)!=EOF)
    {
        gets(pattern+2);
        pattern[1]=cu;
        cmp=0;
        for(i=1;i<=n;i++)
            cmp=(cmp*3+num(pattern[i]))%mod1;
        if(viz[cmp])
            continue;
        st=1;
        dr=numerus-n+1;
        while(st<dr)
        {
            med=(st+dr)/2;
            if(sp[med]<cmp)
                st=med+1;
            else
                dr=med;
        }
        med=(st+dr)/2;
        if(sp[med]<cmp)
            med++;
        while(sp[med]==cmp)
        {
            cnt++;
            viz[cmp]=1;
            med++;
        }
    }
    printf("%d",cnt);
}