Pagini recente » Cod sursa (job #1603222) | Cod sursa (job #2438287) | Cod sursa (job #1872008) | Cod sursa (job #572393) | Cod sursa (job #103292)
Cod sursa(job #103292)
#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;
}