Cod sursa(job #481531)

Utilizator andra23Laura Draghici andra23 Data 31 august 2010 20:33:22
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<vector>
#define maxn 10000010
#define max 23
#define r 33333331
#define b 3
#define rh 666013

using namespace std;

vector<int> h[rh+5];
char a[maxn];
char s[max];

int main(){
    freopen("abc2.in", "r", stdin);
    ofstream g("abc2.out");
    int i, j, k, poz, cod, l;
    long long val;
    fgets (a, maxn, stdin);
    
    fgets(s, max, stdin);
    l = strlen(s)-1;
    val = 0;
    for (i = 0; i < l; i++)
        val = val*b+s[i]-97;
    poz = val%rh;
    h[poz].push_back(val);
    while (!feof(stdin)) {
        fgets(s, max, stdin);
        val = 0;
        for (i = 0; i < l; i++)
            val = val*b+s[i]-97;
        poz = val%rh;
        cod = 1;
        for (i=0; i<h[poz].size(); i++)
            if (h[poz][i] == val){
                cod = 0;
                break;
            }
        if (cod==1)
            h[poz].push_back(val);
    }
    
    int nr = 0;
    val = 0;
    for (i = 0; i<l; i++)
        val = val*b+a[i]-97;
    poz = val%rh;
    for (i=0; i<h[poz].size(); i++)
        if (h[poz][i] == val)
            nr++;
    int pre = 1;
    for (i = 1; i <= l-1; i++)
        pre=pre*b;    
    
    int la = strlen(a)-1;      
    for (i = l; i<la; i++){
        val = val - pre*(a[i-l]-97);
        val = val*b+a[i]-97;
        poz = val%rh;
        for (j=0; j<h[poz].size(); j++)
            if (h[poz][j] == val)
                nr++;     
    }
    
    g<<nr<<endl;
    
    return 0;
}