Pagini recente » Cod sursa (job #2553256) | Cod sursa (job #1046823) | Cod sursa (job #3142070) | Cod sursa (job #686673) | Cod sursa (job #1198590)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string.h>
#define MULT 10000000
using namespace std;
vector<unsigned int> a[MULT];
unsigned int v[50001];
char s[MULT+1];
char cuv[21];
unsigned int p;
int cb(int x){
int st,dr,m;
st=0;
dr=a[x].size()-1;
while(st<dr){
m=(st+dr)/2;
if (a[x][m]==p) return m;
if (a[x][m]<p) st=m+1;
else dr=m;
}
return st;
}
int main(){
freopen ("abc2.in","r",stdin);
freopen ("abc2.out","w",stdout);
int n,m,i,l,cnt;
unsigned int put,j;
scanf ("%s\n",&s);
n=strlen(s);
for(i=0;i<n;i++) s[i]=s[i]-'a';
scanf ("%s\n",&cuv);
l=strlen(cuv);
m=2;
put=1;
v[1]=cuv[l-1]-'a';
for(i=l-2;i>=0;i--){
put*=3;
v[1]=v[1]+(put*(cuv[i]-'a'));
}
while(scanf("%s\n",&cuv)!=EOF){
put=1;
v[m]=cuv[l-1]-'a';
for(i=l-2;i>=0;i--){
put*=3;
v[m]=v[m]+(put*(cuv[i]-'a'));
}
m++;
}
sort(v+1,v+m);
j=v[m-1]+1;
for(i=2;i<m;i++)
if (v[i]==v[i-1]) v[i-1]=j;
sort(v+1,v+m);
for(m--;v[m]==j;) m--;
for(i=1;i<=m;i++)
a[v[i]%MULT].push_back(v[i]);
put=1;
p=s[l-1];
for(i=l-2;i>=0;i--){
put*=3;
p=p+(put*s[i]);
}
cnt=0;
if (a[p%MULT][cb(p%MULT)]==p) cnt++;
for(i=l;i<n;i++){
p=p-(put*s[i-l]);
p*=3;
p=p+s[i];
if (a[p%MULT].empty()!=true)
if (a[p%MULT][cb(p%MULT)]==p) cnt++;
}
printf ("%d",cnt);
return 0;
}