Cod sursa(job #294535)

Utilizator otilia_sOtilia Stretcu otilia_s Data 2 aprilie 2009 16:56:51
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream.h>
#include <string.h>
const long MOD=99987;
long baza=3;
typedef struct nod {int val; nod *urm;} *Lista;
Lista h[100000];
char T[10000004],cuv[25];
int m;

void inserare(long long x)
{
 Lista q=new nod;
 q->val=x; q->urm=h[x%MOD]; h[x%MOD]=q;
}

int potrivire(long long 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))
  {
   long long ind=0;
   for (i=0;cuv[i];++i)
    {
     ind=(ind*baza)+(cuv[i]-'a');
    }
   inserare(ind);
   fin>>cuv;
  }
 int S=0,k;
 long long t0=0;
 for (i=0;i<m;++i)
  t0=(t0*baza)+(T[i]-'a');
 long long 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;
}