Cod sursa(job #103292)

Utilizator pikuAnca Miihai piku Data 15 noiembrie 2007 11:04:31
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.9 kb
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

#define MOD 50

string sir;
//vector<string> sub;
set<string> s;
multimap<int, string> sub;

int hash(string s)
{
 //cout<<"hash "<<s;
int h=0, i, n=s.size();
for(i=0; i<n; i++) {
 h=(h*3+(s[i]-'a'))%MOD;
 //h+=(int) s[i]-'a';
 //cout<<" "<<h;
}
//cout<<endl;
return h%MOD;
}

int hashs(string s, int j)
{
/*
int h=0, i;
for(i=0; i<j; i++)
 h=(h*3+(s[i]-'a'))%MOD;
return h;
*/
return hash(s.substr(0,j));
}

int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
string x;
int i, m, n;

getline(cin, sir);
while(!feof(stdin))
{
 getline(cin, x);
 //sub.push_back(x);
 if(x.size())
 {
  s.insert(x);
  m++;
 }
}

set<string>::iterator it;
for(it=s.begin(); it!=s.end(); it++)
 sub.insert(pair<int,string>(hash(*it), *it));
m=s.size();
n=sir.size();

int hs, l=(*s.begin()).size();
int count=0;

multimap<int,string>::iterator itt;
pair<multimap<int,string>::iterator,multimap<int,string>::iterator> ret;

/*
for ( itt=sub.begin() ; itt != sub.end(); itt++ )
    cout << (*itt).first << " => " << (*itt).second << endl;
cout<<endl;
*/

hs=hash(sir.substr(0, l));
for(i=0; i<n-m+1; i++)
 {
 if(sub.count(hs))
  {ret = sub.equal_range(hs);
   for (itt=ret.first; itt!=ret.second; ++itt)
    {if(sir.substr(i,l)==(*itt).second)
      {count++;
      //cout<<i<<" "<<(*itt).second<<endl;
       break;
     }
    }
    //*/
  }
  //printf("\n");
  //  cout<<sir.substr(i, l);
  //printf(" %d %d ", hs, hash(sir.substr(i, l)));

  //hs=(hs - (sir[i]-'a') + (sir[i+l]-'a'))%MOD;
  //printf("%d %d %d", (sir[i]-'a'), ((sir[i]-'a') * (int) pow(3.0,l-1)), (sir[i+l]-'a'));
  //hs=((hs - ((sir[i]-'a') * (int) pow(3.0,l-1)) )*3 + (sir[i+l]-'a'))%MOD;
  hs-= ((sir[i]-'a') * (int) pow(3.0,l-1))%MOD;
  hs*=3;
  hs+=(sir[i+l]-'a');
  hs%=MOD;
 }
 
printf("%d", count);
return 0;
}