Pagini recente » Cod sursa (job #311156) | Cod sursa (job #2813797) | Cod sursa (job #1379234) | Cod sursa (job #2307432) | Cod sursa (job #1500688)
#include <fstream>
#include <string.h>
#include <algorithm>
#define dim 10000010
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int i,j,n,m,val,sol,nr,po,cod[dim];
char s[dim],c[22];
bool viz[dim];
int binsrch(int x)
{
int st=1,dr=n-m,mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(x<cod[mij])
dr=mij-1;
else
if(x>cod[mij])
st=mij+1;
else
return 1;
}
return 0;
}
int main()
{
fin>>(s+1);
fin>>(c+1);
n=strlen(s+1);
m=strlen(c+1);
po=1;
for(i=1;i<=m;i++)
{
nr=nr*3+s[i]-'a';
val=val*3+c[i]-'a';
po*=3;
}
po/=3;
for(i=m+1;i<=n;i++)
{
cod[i-m]=nr;
nr=(nr-po*(s[i-m]-'a'))*3+s[i]-'a';
}
sort(cod+1,cod+n-m+1);
viz[val]=1;
if(binsrch(val))
sol++;
while(fin>>(c+1))
{
val=0;
for(i=1;i<=m;i++)
{
val=val*3+c[i]-'a';
if(viz[val]==0)
{
viz[val]=1;
if(binsrch(val))
sol++;
}
}
}
fout<<sol;
return 0;
}