Pagini recente » Cod sursa (job #1651014) | Cod sursa (job #1417305) | Cod sursa (job #3289577) | Cod sursa (job #1548770) | Cod sursa (job #3210236)
#include <fstream>
#include <cstring>
#include <vector>
#define base 54
#define m1 100013
#define m2 100009
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector<int> rasp;
char s1[2000001],s2[2000001];
int nrs1,nrs2,p1,p2;
int main()
{
cin.get(s1,2000001);
cin.get();
cin.get(s2,2000001);
int ls1=strlen(s1);
int ls2=strlen(s2);
nrs1=nrs2=0;
p1=p2=1;
for(int i=0;i<ls1;i++){
nrs1=(nrs1*base+s1[i])%m1;
nrs2=(nrs2*base+s1[i])%m2;
if(i>0){
p1=p1*base%m1;
p2=p2*base%m2;
}
}
if(ls1>ls2){
cout<<0;
}else{
int nr1=0,nr2=0;
for(int i=0;i<ls1;i++){
nr1=(nr1*base+s2[i])%m1;
nr2=(nr2*base+s2[i])%m2;
}
if(nr1==nrs1&&nr2==nrs2){
rasp.push_back(0);
}
for(int i=ls1;i<ls2;i++){
nr1=((nr1-(s2[i-ls1]*p1)%m1+m1)*base+s2[i])%m1;
nr2=((nr2-(s2[i-ls1]*p2)%m2+m2)*base+s2[i])%m2;
if(nr1==nrs1&&nr2==nrs2){
rasp.push_back(i-ls1+1);
}
}
cout<<rasp.size()<<"\n";
ls2=rasp.size();
for(int i=0;i<ls2&&i<1000;i++){
cout<<rasp[i]<<" ";
}
}
}