Pagini recente » Cod sursa (job #3138368) | Cod sursa (job #1814494) | Cod sursa (job #1324435) | Cod sursa (job #1767476) | Cod sursa (job #2977183)
#include <fstream>
#include <cstring>
#define DIM 2000005
#define mod 779993
#define mod1 999773
#define baza 79
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long n,m,p,p1,h1,hh1,h2,hh2,cnt,sol[DIM];
char a[DIM],b[DIM];
int main() {
fin>>a>>b;
n=strlen(a);
m=strlen(b);
if (n>m) {
fout<<0;
return 0;
}
p=p1=1;
for (int i=0;i<n;i++) {
h1=(h1*baza+a[i])%mod;
hh1=(hh1*baza+a[i])%mod1;
h2=(h2*baza+b[i])%mod;
hh2=(hh2*baza+b[i])%mod;
if (i!=0) {
p=p*baza%mod;
p1=p1*baza%mod1;
}
}
if (h1==h2 && hh1==hh2)
sol[++cnt]=0;
for (int i=n;i<m;i++) {
h2=((h2-(b[i-n]*p)%mod+mod)*baza+b[i])%mod;
hh2=((hh2-(b[i-n]*p1)%mod1+mod1)*baza+b[i])%mod1;
if (h1==h2 && hh1==hh2)
sol[++cnt]=i-n+1;
}
fout<<cnt<<"\n";
for (int i=1;i<=cnt && i<=1000;i++)
fout<<sol[i]<<" ";
return 0;
}