Pagini recente » Istoria paginii utilizator/florea.florin | Cod sursa (job #392092) | Cod sursa (job #168538) | Cod sursa (job #966427) | Cod sursa (job #3041264)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
#define cin fin
#define cout fout
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int BASE=77;
const int MOD1=100007;
const int MOD2=100021;
vector<int>v;
string a;
string b;
int lgput(int a,int b,int MODU)
{
int total;
if(b==0)
return 1;
else
{
if(b%2==0)
{
total=lgput(a,b/2,MODU)%MODU;
total=1LL*total*total%MODU;
return total;
}
else
{
total=lgput(a,b/2,MODU)%MODU;
total=1LL*total*total%MODU;
return 1LL*total*a%MODU;
}
}
}
void rabin(int n,int m)
{
int i,j,hash1a=0,hash1b=0,hash2a=0,hash2b=0,p1,p2;
for(i=0;i<n;i++)
{
hash1a=(hash1a*BASE+a[i])%MOD1;
hash2a=(hash2a*BASE+a[i])%MOD2;
hash1b=(hash1b*BASE+b[i])%MOD1;
hash2b=(hash2b*BASE+b[i])%MOD2;
}
if(hash1a==hash1b && hash2a==hash2b)
v.push_back(0);
p1=lgput(BASE,n-1,MOD1);
p2=lgput(BASE,n-1,MOD2);
for(i=n;i<=m;i++)
{
hash1b=((hash1b-(b[i-n]*p1)%MOD1+MOD1)*BASE+b[i])%MOD1;
hash2b=((hash2b-(b[i-n]*p2)%MOD2+MOD2)*BASE+b[i])%MOD2;
if(hash1a==hash1b && hash2a==hash2b)
v.push_back(i-n+1);
}
}
int main()
{
int i,j,n,m,debuff=0;
cin>>a>>b;
n=a.size();
m=b.size();
rabin(n,m);
cout<<v.size()<<"\n";
for(auto i:v)
{
debuff++;
cout<<i<<" ";
if(debuff==1000)
exit(0);
}
return 0;
}