Pagini recente » Cod sursa (job #1565904) | Cod sursa (job #612447) | Monitorul de evaluare | Cod sursa (job #2854895) | Cod sursa (job #975751)
Cod sursa(job #975751)
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#define KEY1 100007
#define KEY2 100021
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)
rez[++rez[0]]=0;
for(int i=n;i<m;++i)
{
string_hash1=((string_hash1*base - (get_val(y[i-n])*p1)%KEY1 + KEY1 ) +get_val(y[i]))%KEY1;
string_hash2=((string_hash2*base - (get_val(y[i-n])*p2)%KEY2 + KEY2 ) +get_val(y[i]))%KEY2;
//cout<<" I :"<<i<<" DDD "<<string_hash1<<" ->"<<pattern_hash1<<" | "<<string_hash2<<" ->"<<pattern_hash2<<endl;
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;
}