Pagini recente » Profil Nicolaalexandra | Monitorul de evaluare | patrol2 | Monitorul de evaluare | Cod sursa (job #294553)
Cod sursa(job #294553)
#include <fstream>
#include <string.h>
using namespace std;
const unsigned MOD=48991;
unsigned baza=3;
typedef struct nod {unsigned val; nod *urm;} *Lista;
Lista h[50000];
char T[10000004],cuv[25];
int m;
void inserare(unsigned x)
{
Lista q=new nod;
q->val=x; q->urm=h[x%MOD]; h[x%MOD]=q;
}
int potrivire(unsigned x)
{
Lista q=h[x%MOD];
while (q!=NULL)
{
if (q->val==x) return 1;
q=q->urm;
}
return 0;
}
int main()
{
ifstream fin("abc2.in");
fin>>T;
int n=strlen(T);
int i;
fin>>cuv; m=strlen(cuv);
while (strlen(cuv))
{
unsigned ind=0;
for (i=0;cuv[i];++i)
{
ind=(ind*baza)+(cuv[i]-'a');
}
inserare(ind);
fin>>cuv;
}
int S=0,k;
unsigned t0=0;
for (i=0;i<m;++i)
t0=(t0*baza)+(T[i]-'a');
unsigned z=1;
for (i=1;i<m;++i) z*=baza;
for (k=0;k<=n-m;++k)
{
if (h[t0%MOD]!=NULL)
if (potrivire(t0)) ++S;
t0=(t0-(T[k]-'a')*z)*baza+(T[k+m]-'a');
}
ofstream fout("abc2.out");
fout<<S<<"\n";
fin.close(); fout.close();
return 0;
}