Cod sursa(job #481189)

Utilizator andra23Laura Draghici andra23 Data 30 august 2010 20:43:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<vector>
#define maxn 10000010
#define max 23
#define r 333333313
#define b 29
#define rh 666013

using namespace std;

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

int main(){
    FILE *f = fopen("abc2.in", "r");
    ofstream g("abc2.out");
    int i, j, k, val, poz, cod, l;
    fscanf(f, "%s", a);
    while (!feof(f)) {
        fscanf(f, "%s", s);
        val = 0;
        for (i = 0; i < strlen(s); i++)
            val = (val*b+s[i]-97)%r;
        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);
    }
    l = strlen(s);
    int nr = 0;
    
    val = 0;
    for (i = 0; i<l; i++)
        val = (val*b+a[i]-97)%r;
    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)%r;    
          
    for (i = l; i<strlen(a); i++){
        val = val - (pre*(a[i-l]-97))%r;
        if (val < 0)
            val = val+r;
        val = (val*b+a[i]-97)%r;
        poz = val%rh;
        for (j=0; j<h[poz].size(); j++)
            if (h[poz][j] == val)
                nr++;     
    }
    
    g<<nr<<endl;
    
    return 0;
}