Pagini recente » Cod sursa (job #1704042) | Cod sursa (job #182989) | Cod sursa (job #1472531) | Cod sursa (job #1554746) | Cod sursa (job #975749)
Cod sursa(job #975749)
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#define KEY1 660013
#define KEY2 11213
using namespace std;
string x,y;
int rez[1005];
int get_val(char x)
{
if(islower(x))
return (x-'a')+1;
return (x-'A')+27;
}
int main()
{
int base=52,n,m;
long long pattern_hash1=0,pattern_hash2=0,string_hash1=0,string_hash2=0,p1=1,p2=1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f,x);
getline(f,y);
n=x.size();
m=y.size();
for(int i=0;i<n;++i)
{
pattern_hash1=(pattern_hash1*base+get_val(x[i]))%KEY1;
pattern_hash2=(pattern_hash2*base+get_val(x[i]))%KEY2;
p1=(p1*base)%KEY1;
p2=(p2*base)%KEY2;
}
for(int i=0;i<n;++i)
{
string_hash1=(string_hash1*base+get_val(y[i]))%KEY1;
string_hash2=(string_hash2*base+get_val(y[i]))%KEY2;
}
if(string_hash1==pattern_hash1 && string_hash2==pattern_hash2)
cout<<0<<endl;
for(int i=n;i<m;++i)
{
string_hash1=((string_hash1*base - (get_val(y[i-n])*p1)%KEY1 + KEY1 )%KEY1 +get_val(y[i]))%KEY1;
string_hash2=((string_hash2*base - (get_val(y[i-n])*p2)%KEY2 + KEY2 )%KEY2 +get_val(y[i]))%KEY2;
if(string_hash1==pattern_hash1 && string_hash2==pattern_hash2 && rez[0]<1000)
rez[++rez[0]]=i-n+1;
}
g<<rez[0]<<"\n";
for(int i=1;i<=rez[0];++i)
g<<rez[i]<<" ";
return 0;
}