Cod sursa(job #1198590)

Utilizator livliviLivia Magureanu livlivi Data 16 iunie 2014 11:51:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string.h>
#define MULT 10000000
using namespace std;
vector<unsigned int> a[MULT];
unsigned int v[50001];
char s[MULT+1];
char cuv[21];
unsigned int p;
int cb(int x){
    int st,dr,m;
    st=0;
    dr=a[x].size()-1;
    while(st<dr){
        m=(st+dr)/2;
        if (a[x][m]==p) return m;
        if (a[x][m]<p) st=m+1;
        else dr=m;
    }
    return st;
}
int main(){
    freopen ("abc2.in","r",stdin);
    freopen ("abc2.out","w",stdout);
    int n,m,i,l,cnt;
    unsigned int put,j;
    scanf ("%s\n",&s);
    n=strlen(s);
    for(i=0;i<n;i++) s[i]=s[i]-'a';
    scanf ("%s\n",&cuv);
    l=strlen(cuv);
    m=2;
    put=1;
    v[1]=cuv[l-1]-'a';
    for(i=l-2;i>=0;i--){
        put*=3;
        v[1]=v[1]+(put*(cuv[i]-'a'));
    }
    while(scanf("%s\n",&cuv)!=EOF){
        put=1;
        v[m]=cuv[l-1]-'a';
        for(i=l-2;i>=0;i--){
            put*=3;
            v[m]=v[m]+(put*(cuv[i]-'a'));
        }
        m++;
    }
    sort(v+1,v+m);
    j=v[m-1]+1;
    for(i=2;i<m;i++)
        if (v[i]==v[i-1]) v[i-1]=j;
    sort(v+1,v+m);
    for(m--;v[m]==j;) m--;
    for(i=1;i<=m;i++)
        a[v[i]%MULT].push_back(v[i]);
    put=1;
    p=s[l-1];
    for(i=l-2;i>=0;i--){
        put*=3;
        p=p+(put*s[i]);
    }
    cnt=0;
    if (a[p%MULT][cb(p%MULT)]==p) cnt++;
    for(i=l;i<n;i++){
        p=p-(put*s[i-l]);
        p*=3;
        p=p+s[i];
        if (a[p%MULT].empty()!=true)
            if (a[p%MULT][cb(p%MULT)]==p) cnt++;
    }
    printf ("%d",cnt);
    return 0;
}