Pagini recente » Cod sursa (job #1040296) | Cod sursa (job #1505627) | Cod sursa (job #715142) | Cod sursa (job #1363208) | Cod sursa (job #3226671)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
#define cin fin
#define cout fout
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MOD1=666013;
const int MOD2=1e5+7;
const int NMAX=2e6+5;
const int BASE=73;
string a;
string b;
vector<int>v;
void rabin(int n,int m)
{
int i,j;
int hash1a=0,hash1b=0,hash2a=0,hash2b=0,p1=1,p2=1;
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(i!=0)
{
p1=p1*BASE%MOD1;
p2=p2*BASE%MOD2;
}
}
if(hash1a==hash1b && hash2a==hash2b)
v.push_back(0);
for(i=n;i<=m;i++)
{
hash1b=(((hash1b-(b[i-n]*p1%MOD1)+MOD1)%MOD1)*BASE+b[i])%MOD1;
hash2b=(((hash2b-(b[i-n]*p2%MOD2)+MOD2)%MOD2)*BASE+b[i])%MOD2;
if(hash1a==hash1b && hash2a==hash2b)
v.push_back(i-n+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,i,j,m;
cin>>a>>b;
n=a.size();
m=b.size();
rabin(n,m);
cout<<v.size()<<"\n";
int debuff=0;
for(auto i:v)
{
debuff++;
cout<<i<<" ";
if(debuff==1000)
break;
}
return 0;
}