Cod sursa(job #247244)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 22 ianuarie 2009 17:30:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <string>
#include <vector>
#define mod 666013
#define pb push_back
using namespace std;
// nr max 3 486 784 401
struct elem{unsigned int v;int c;};
int n,m,i,sol,p3[21]; char text[10000005],ch[32];
unsigned int nr; elem ax;
vector <elem>v[mod];

void add(unsigned int x){
   unsigned k=x%mod,i,l=v[k].size(),ok=0;
   for (i=0;i<l;++i)if (v[k][i].v==x){ok=1;break;}
   if (ok)v[k][i].c++;
   else {ax.v=x;ax.c=1;v[k].pb(ax);}
}
void search(unsigned int x){
   unsigned k=x%mod,i,l=v[k].size(),ok=0;
   for (i=0;i<l;++i)if (v[k][i].v==x){ok=1;break;}
   if (ok){sol+=v[k][i].c;v[k][i].c=0;}
}

int main(){
   freopen("abc2.in","r",stdin);
   freopen("abc2.out","w",stdout);
   scanf("%s\n",text);n=strlen(text);
   scanf("%s\n",ch);m=strlen(ch);
  //preprocesare
  for (p3[0]=1,i=1;i<=20;++i)p3[i]=p3[i-1]*3;
  for (i=0;i<m;++i)
	 nr=nr*3+text[i]-'a';
  add(nr);
  for (i=m;i<n;++i){
	 nr-=p3[m-1]*(text[i-m]-'a');
	 nr=nr*3+text[i]-'a';
	 add(nr);
  }
  //
  while (ch[0]){
	 for (i=0,nr=0;i<m;++i) nr=nr*3+ch[i]-'a';
	 search(nr);
     ch[0]=0;
	 scanf("%s\n",ch);
  }
  printf("%ld\n",sol);
}