Pagini recente » Cod sursa (job #2029576) | Cod sursa (job #2540977) | Cod sursa (job #1409819) | Cod sursa (job #895048) | Cod sursa (job #2865080)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[2000001];
char s2[2000001];
int v[2000001];
int nr=0;
void rabin_karp(char s1[], char s2[])
{
int h1=0,h2=0,l1=strlen(s1), l2=strlen(s2);
int putere=1;
int baza=256;
int mod=1007;
bool ok;
for(int i=0;i<l1;i++)
{
if(i!=1) putere=(putere*baza)%mod;
h1=((h1*baza)+s1[i])%mod;
h2=((h2*baza)+s2[i])%mod;
}
for(int i=0;i<=l2-l1;i++)
{
if(h1==h2){
ok=true;
for(int j=0;j<l1;j++)
if(s1[j]!=s2[j+i]){
ok=false;
break;
}
if(ok){
nr++;
v[i]=1;
}
}
else{
h2=((h2-s2[i]*putere)*baza + s2[i+l1])%mod;
if(h2<0) h2=h2+mod;
}
}
}
int main()
{
cin.get(s1,100);
cin.get();
cin.get(s2,100);
if(strlen(s1)>strlen(s2)){
cout<<"0";
return 0;
}
rabin_karp(s1,s2);
cout<<nr<<" "<<endl;
nr=0;
for(int i=0;i<=strlen(s2) && nr<1000;i++)
{
if(v[i]) cout<<i<<" ";
nr++;
}
cin.close();
cout.close();
return 0;
}