Pagini recente » Cod sursa (job #202045) | Cod sursa (job #278321) | Cod sursa (job #1594967) | Diferente pentru warm-up-2019/solutii/shoturi intre reviziile 54 si 55 | Cod sursa (job #3041245)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#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=27;
const int MOD=1e5+7;
vector<int>v;
string a;
string b;
int lgput(int a,int b)
{
int total;
if(b==0)
return 1;
else
{
if(b%2==0)
{
total=lgput(a,b/2)%MOD;
total=1LL*total*total%MOD;
return total;
}
else
{
total=lgput(a,b/2)%MOD;
total=1LL*total*total%MOD;
return 1LL*total*a%MOD;
}
}
}
void rabin(int n,int m)
{
int i,j,hasha=0,hashb=0,p;
for(i=0;i<n;i++)
{
hasha=(hasha*BASE+(a[i]-'0'))%MOD;
hashb=(hashb*BASE+(b[i]-'0'))%MOD;
}
if(hasha==hashb)
v.push_back(0);
p=lgput(BASE,n-1);
for(i=n;i<m;i++)
{
hashb=((hashb-((b[i-n]-'0')*p)%MOD+MOD)*BASE+(b[i]-'0'))%MOD;
if(hashb==hasha)
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;
}