Pagini recente » Cod sursa (job #495578) | Cod sursa (job #1427893) | Cod sursa (job #43667) | Cod sursa (job #2428285) | Cod sursa (job #2536071)
#include<bits/stdc++.h>
using namespace std;
#define MOD1 100007
#define MOD2 100021
#define MAX 74
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string text,pattern;
void read()
{
in>>pattern>>text;
}
void rabin_karp()
{
int base1=1,base2=1;
long long basemod1=0,basemod2=0;
vector<int> results;
for(int i=0; i<pattern.length(); i++)
{
basemod1=(basemod1*MAX+pattern[i])%MOD1;
basemod2=(basemod2*MAX+pattern[i])%MOD2;
if(i)
{
base1=(base1*MAX)%MOD1;
base2=(base2*MAX)%MOD2;
}
}
long long mod1=0,mod2=0;
for(int i=0; i<pattern.length(); i++)
{
char here=text[i];
mod1=(mod1*MAX+here)%MOD1;
mod2=(mod2*MAX+here)%MOD2;
}
if(basemod1==mod1 && basemod2==mod2)
{
results.push_back(0);
}
char last=text[0];
for(int i=1; i<text.length()-pattern.length()+1; i++)
{
long long delete1=(base1*last)%MOD1;
long long delete2=(base2*last)%MOD2;
mod1=(((mod1-delete1+MOD1)*MAX)%MOD1+text[i+pattern.length()-1])%MOD1;
mod2=(((mod2-delete2+MOD2)*MAX)%MOD2+text[i+pattern.length()-1])%MOD2;
if(mod1==basemod1 && mod2==basemod2)
{
results.push_back(i);
}
last=text[i];
}
out<<results.size()<<endl;
int ending=results.size();
ending=min(ending,1000);
for(int i=0; i<ending; i++)
{
out<<results[i]<<" ";
}
}
int main()
{
read();
if(pattern.length()>text.length())
out<<0;
else
rabin_karp();
}