Cod sursa(job #1518855)

Utilizator lauratalaatlaura talaat lauratalaat Data 6 noiembrie 2015 15:24:13
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long n1=100007,n2=100021,b=3;
struct bine { long long numar1 , numar2 ;};
bine v[50001];
bool sortare ( bine a , bine b ){
    if(a.numar1!=b.numar1)
        return a.numar1<b.numar1;
    return a.numar2<b.numar2;
}
long long k;
char s[10000001],s1[21];
int gasire( long long a1 , long long b1){
    long long pp,i,st,dr,m;
    st=1;
    dr=k;
    pp=1;
    while(st<=dr&&pp==1){
      m=(st+dr)/2;
      if(v[m].numar1==a1&&v[m].numar2==b1)
          pp=0;
      else
        if(v[m].numar1>a1)
          dr=m-1;
        else
          st=m+1;
    }
    if(pp==0)
        return 1;
    return 0;
}
int main(){
    long long  nr1,nr2,p1,p2,n,i,k1,k2,nnr1,nnr2,r,cate,j;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    scanf("%s",&s);k=0;
    nr1=nr2=0;
    p1=p2=1;
    while(scanf("%s",&s1)!=EOF){
        n=strlen(s1); nr1=nr2=0; p1=p2=1;
        for(i=0;i<n;i++){
            nr1=((nr1*b)%n1+s1[i]-'a'+1)%n1;
            nr2=((nr2*b)%n2+s1[i]-'a'+1)%n2;
            if(i!=0){
                p1=(p1*b)%n1;
                p2=(p2*b)%n2;
            }
        }
        k++;
        v[k].numar1=nr1;
        v[k].numar2=nr2;
    }
    sort(v+1,v+k+1,sortare);
    k1=n;
    n=strlen(s);
    nnr1=nnr2=0;
    k2=0;cate=0;
    for(i=0;i<k1;i++){
        nnr1=((nnr1*b)%n1+(s[i]-'a'+1))%n1;
        nnr2=((nnr2*b)%n2+(s[i]-'a'+1))%n2;
    }
    r=0;
    r=gasire(nnr1,nnr2);
    if(r!=0)
        cate++;
    for(i=0,j=k1;j<n;i++,j++){
        nnr1=((((nnr1-((s[i]-'a'+1)*p1))*b)%n1+n1)%n1+(s[j]-'a'+1))%n1;
        nnr2=((((nnr2-((s[i]-'a'+1)*p2))*b)%n2+n2)%n2+(s[j]-'a'+1))%n2;
        r=0;
        r=gasire(nnr1,nnr2);
        if(r!=0)
            cate++;
    }
    printf("%lld\n",cate);
    return 0;
}