Pagini recente » Cod sursa (job #2398960) | Cod sursa (job #1657349) | Cod sursa (job #299588) | Cod sursa (job #2094874) | Cod sursa (job #253341)
Cod sursa(job #253341)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define N 50007
int v[30],enc[N];
char s[200*N],dict[30];
int n,m,k,val,nr;
int caut_bin(int *q,int l,int c){
int op,r=1;
for(op=1;op<l;op<<=1);
for(;op;op>>=1)
if((r+op<=l)&&(q[r+op]<=c))
r+=op;
if(q[r]==c)
return 1;
return 0;
}
void calc(){
int i;
for(i=1;i<=n-m+1;++i){
val-=v[m-1]*(s[i-1]-'s');
val=val*3+s[i+m-1]-'s';
if(caut_bin(enc,k,val))
nr++;
}
printf("%d\n",nr);
}
int add(int m,char *s){
int i,p=0;
for(i=0;i<m;++i)
p+=v[m-i-1]*(s[i]-'s');
return p;
}
void citire(){
int i;
scanf("%s",s);
scanf("%s",dict);
n=strlen(s);
m=strlen(dict);
v[0]=1;
for(i=1;i<=m;++i)
v[i]=v[i-1]*3;
enc[1]=add(m,dict);
k=1;
while(scanf("%s",dict)!=EOF){
enc[++k]=add(m,dict);
}
}
int main(){
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
citire();
std::sort(enc+1,enc+1+k);
val=add(m,s);
if(caut_bin(enc,k,val))
nr=1;
calc();
fclose(stdin);
fclose(stdout);
return 0;
}