Pagini recente » Cod sursa (job #2785840) | Cod sursa (job #1890014) | Cod sursa (job #792140) | Cod sursa (job #968047) | Cod sursa (job #1483514)
#include <stdio.h>
#define MAXT 100000000
#define MAXL 20
#define MAXN 50000
#define MOD 666013
#define BASE 598729
char text[MAXT + 2], cuv[MAXN + 1][MAXL + 2];
int next[MAXN], ult[MOD];
inline char same(int st, int dr, int c){
int i;
for(i = st; i <= dr; i++)
if(text[i] != cuv[c][i - st])
return 0;
return 1;
}
inline char lit(char ch){
if(ch >= 'a' && ch <= 'z')
return 1;
return 0;
}
int main(){
FILE *in = fopen("abc2.in", "r");
fgets(text, MAXT + 2, in);
int nr = 0;
char g = 1;
while(g){
fgets(cuv[nr], MAXL + 2, in);
if(!lit(cuv[nr][0]))
g = 0;
nr++;
}
nr--;
fclose(in);
int i, j, l = 0, h;
while(lit(cuv[0][l]))
l++;
for(i = 0; i < MOD; i++)
ult[i] = -1;
for(i = 0; i < nr; i++){
h = 0;
for(j = 0; j < l; j++)
h = (1LL * h * BASE + cuv[i][j] - 'a' + 1) % MOD;
next[i] = ult[h];
ult[h] = i;
}
int rez = 0, poz, ptr = 1, ad;
for(i = 0; i < l; i++)
ptr = 1LL * ptr * BASE % MOD;
h = 0;
for(i = 0; i < l - 1; i++)
h = (1LL * h * BASE + text[i] - 'a' + 1) % MOD;
for(i = l - 1; lit(text[i]); i++){
h = (1LL * h * BASE + text[i] - 'a' + 1) % MOD;
if(i - l >= 0)
h -= (text[i - l] - 'a' + 1) * ptr % MOD;
if(h < 0)
h += MOD;
poz = ult[h];
ad = 0;
while(poz > -1){
if(same(i - l + 1, i, poz))
ad = 1;
poz = next[poz];
}
rez += ad;
}
FILE *out = fopen("abc2.out", "w");
fprintf(out, "%d", rez);
fclose(out);
return 0;
}