Pagini recente » Arhiva de probleme | Cod sursa (job #1245946) | Cod sursa (job #1030766) | Cod sursa (job #2952840) | Cod sursa (job #1984740)
//BAZA 3
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod1=666013;
const int mod2=363277;
const int nmax=10000005;
bool viz[666013];
char c[nmax],pattern[25];
int sp[nmax];
inline short int num(char ch)
{
return ch-'a';
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
int n,i,j,putere=1,nr=0,cmp=0,cmp2=0,nr2=0,putere2,numerus,cnt=0,med,st,dr;
bool ok=0;
char cu;
gets(c+1);
numerus=strlen(c+1);
gets(pattern+1);
n=strlen(pattern+1);
for(i=1;i<=n;i++)
{
nr=(nr*3+num(c[i]))%mod1;
cmp=(cmp*3+num(pattern[i]))%mod1;
if(i!=1)
{
putere=putere*3%mod1;
}
}
sp[1]=nr;
if(sp[1]==cmp)
{
cnt++;
viz[cmp]++;
}
for(i=n+1;i<=numerus;i++)
{
sp[i-n+1]=(((sp[i-n]-(num(c[i-n])*putere)%mod1+mod1)%mod1)*3 + num(c[i]))%mod1;
if(sp[i-n+1]==cmp)
{
cnt++;
viz[cmp]=1;
}
}
sort(sp+1,sp+numerus+1-n);
while(scanf("%c",&cu)!=EOF)
{
gets(pattern+2);
pattern[1]=cu;
cmp=0;
for(i=1;i<=n;i++)
cmp=(cmp*3+num(pattern[i]))%mod1;
if(viz[cmp])
continue;
st=1;
dr=numerus-n+1;
while(st<dr)
{
med=(st+dr)/2;
if(sp[med]<cmp)
st=med+1;
else
dr=med;
}
med=(st+dr)/2;
if(sp[med]<cmp)
med++;
while(sp[med]==cmp)
{
cnt++;
viz[cmp]=1;
med++;
}
}
printf("%d",cnt);
}