Pagini recente » Cod sursa (job #1931392) | Cod sursa (job #231686) | Cod sursa (job #173004) | Cod sursa (job #2213813) | Cod sursa (job #2839320)
#include <bits/stdc++.h>
#define nmax 2000005
#define mod1 98999
#define mod2 99991
#define baza 123
using namespace std;
char A[nmax],B[nmax];
int V[nmax],P[nmax],rsp[nmax];
int ma,mb,h1,h2;
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
f>>A>>B;
ma=strlen(A);
mb=strlen(B);
int r1=0,r2=0,inm1=1,inm2=1,sol=0;
for (int i=0; i<ma; i++)
{
r1=(r1*baza+A[i])%mod1;
r2=(r2*baza+A[i])%mod2;
h1=(h1*baza+B[i])%mod1;
h2=(h2*baza+B[i])%mod2;
if (i==ma-1 && r1==h1 && r2==h2)
sol++,rsp[sol]=i-ma+1;
if (i!=0)
{
inm1=(inm1*baza)%mod1;
inm2=(inm2*baza)%mod2;
}
}
for (int i=ma; i<mb; i++)
{
h1=h1-(B[i-ma]*inm1)%mod1+mod1;
h2=h2-(B[i-ma]*inm2)%mod2+mod2;
h1=(h1*baza+B[i])%mod1;
h2=(h2*baza+B[i])%mod2;
if (r1==h1 && r2==h2)
sol++,rsp[sol]=i-ma+1;
}
g<<sol<<'\n';
sol=min(sol,1000);
for (int i=1; i<=sol; i++)
g<<rsp[i]<<' ';
}