Pagini recente » Istoria paginii runda/oji_2006_10/clasament | Cod sursa (job #355328) | Cod sursa (job #766897) | Cod sursa (job #2843600) | Cod sursa (job #483984)
Cod sursa(job #483984)
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define MAX 10000005
#define MOD 666013
#define LIM 25
#define P 3
vector <unsigned int> h[MOD];
char s[MAX],buff[LIM];
int n,m,nrt;
inline int find (unsigned int val,unsigned int mod)
{
vector <unsigned int> :: iterator it;
for (it=h[mod].begin (); it!=h[mod].end (); ++it)
if (*it==val)
return 1;
return 0;
}
inline void insert (unsigned int val,unsigned int mod)
{
if (!find (val,mod))
h[mod].pb (val);
}
void read ()
{
unsigned int nr;
int i;
fgets (s,MAX,stdin);
n=strlen (s)-1;
for (nr=0; fgets (buff,LIM,stdin); nr=0)
{
m=strlen (buff)-1;
for (i=0; i<m; ++i)
nr=nr*P+buff[i]-'a';
insert (nr,nr%MOD);
}
}
void solve ()
{
unsigned int nr,put;
int i;
nr=0; put=1;
for (i=0; i<m; ++i)
{
nr=nr*P+s[i]-'a';
if (i)
put*=P;
}
for (i=m; i<=n; ++i)
{
nrt+=find (nr,nr%MOD);
nr=(nr-(s[i-m]-'a')*put)*P+(s[i]-'a');
}
printf ("%d",nrt);
}
int main ()
{
freopen ("abc2.in","r",stdin);
freopen ("abc2.out","w",stdout);
read ();
solve ();
return 0;
}