Pagini recente » Cod sursa (job #716824) | Cod sursa (job #213849) | Cod sursa (job #657240) | Cod sursa (job #865555) | Cod sursa (job #105573)
Cod sursa(job #105573)
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define sz(c) (int)((c).size())
#define fin "abc2.in"
#define fout "abc2.out"
const int Nmax = 100;
const int Mmax = 10000010;
int N,ret;
char buff[Nmax];
char txt[Mmax];
vector <unsigned int> v;
void ins(char a[])
{
int i;
unsigned int pt,tmp;
pt=1; tmp=0;
for (i=0;i<N;++i)
{
tmp = tmp + ( a[i] - 'a' ) * pt;
pt *= 3;
}
v.pb(tmp);
}
inline int search(unsigned int val)
{
int i,step;
for ( step = 1 ; step < sz(v) ; step <<= 1 );
for ( i = 0 ; step ; step >>= 1 )
if ( i + step < sz(v) && v[i+step] <= val )
i += step;
if ( v[i] != val ) return -1;
return i;
}
int main()
{
int i;
unsigned int pt,tmp;
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
fgets(txt,Mmax,stdin);
fgets(buff,Nmax,stdin);
for ( i = 0 ; 'a' <= txt[i] && txt[i]<='c' ; ++i )
txt[i]-='a';
while ( 'a' <= buff[N] && buff[N] <= 'c' ) ++ N ;
ins(buff);
while ( !feof(stdin) )
{
fgets(buff,Nmax,stdin);
ins(buff);
}
sort(v.begin(),v.end());
tmp=0; pt=1;
for (i=0;i<N;++i)
{
tmp = tmp + txt[i] * pt;
pt*=3;
}
pt/=3;
if ( search(tmp) != -1 ) ++ret;
for (i=N; 0 <= txt[i] && txt[i] <= 2 ;++i)
{
tmp -= txt[i-N];
tmp /= 3;
tmp = tmp + txt[i]*pt;
if ( search(tmp) != -1 ) ++ret;
}
printf("%d\n",ret);
return 0;
}