Pagini recente » Cod sursa (job #1346981) | Cod sursa (job #1580790) | Cod sursa (job #3307) | Cod sursa (job #3213195) | Cod sursa (job #2346938)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
const int MOD1 = 666013;
const int MOD2 = 1300727;
int n,m;
char A[NMAX];
char B[NMAX];
int rasp[NMAX];
int main()
{
fin >> (A+1);
fin >> (B+1);
n=strlen(A+1);
m=strlen(B+1);
int put1=1,put2=1,baza=71,nr11=0,nr12=0,nr21=0,nr22=0,putere1,putere2;
for(int i=n;i>=1;i--)
{
if(i==1) putere1=put1,putere2=put2;
nr11+=((A[i]-53)*put1)%MOD1;
nr11%=MOD1;
nr12+=((A[i]-53)*put2)%MOD2;
nr12%=MOD2;
put1*=baza;
put2*=baza;
put1%=MOD1;
put2%=MOD2;
}
put1=1,put2=1;
for(int i=n;i>=1;i--)
{
nr21+=((B[i]-53)*put1)%MOD1;
nr21%=MOD1;
nr22+=((B[i]-53)*put2)%MOD2;
nr22%=MOD2;
put1*=baza;
put2*=baza;
put1%=MOD1;
put2%=MOD2;
}
int k=0;
if(nr11==nr21 && nr12==nr22)
{
rasp[++k]=0;
}
for(int i=n+1;i<=m;i++)
{
nr21-=((B[i-n]-53)*putere1)%MOD1;
nr22-=((B[i-n]-53)*putere2)%MOD2;
if(nr21<0) nr21+=MOD1;
if(nr22<0) nr22+=MOD2;
nr21*=baza;
nr22*=baza;
nr21+=(B[i]-53);
nr22+=(B[i]-53);
nr21%=MOD1;
nr22%=MOD2;
if(nr21==nr11 && nr22==nr12)
{
rasp[++k]=i-n;
}
}
fout << k << '\n';
if(k>1000) k=1000;
for(int i=1;i<=k;i++) fout << rasp[i] << ' ';
return 0;
}