Pagini recente » Cod sursa (job #1785492) | Cod sursa (job #1992530) | Cod sursa (job #1644300) | Cod sursa (job #2804737) | Cod sursa (job #481296)
Cod sursa(job #481296)
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<vector>
#define maxn 10000010
#define max 23
#define r 33333331
#define b 29
#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, val, poz, cod, l;
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)%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);
while (!feof(stdin)) {
fgets(s, max, stdin);
val = 0;
for (i = 0; i < l; 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);
}
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;
int la = strlen(a)-1;
for (i = l; i<la; 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;
}