Pagini recente » Cod sursa (job #2579040) | Cod sursa (job #2015638) | Cod sursa (job #1718261) | Cod sursa (job #1403054) | Cod sursa (job #2299086)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int B1=131, M1=666013;
const int B2=127, M2=10013;
const int NMAX=2e6+5;
char A[NMAX], B[NMAX];
int N, M;
long long R1, R11, R2, R22, pow1=1, pow2=1;
int Sol[NMAX], vf;
int i;
int main()
{
f.tie(NULL);
f>>A>>B;
N=(int)strlen(A);
M=(int)strlen(B);
for(i=0; i<N; ++i)
{
R1=R1*B1%M1+(A[i]-'0');
R1%=M1;
R2=R2*B2%M2+(A[i]-'0');
R2%=M2;
R11=R11*B1%M1+(B[i]-'0');
R11%=M1;
R22=R22*B2%M2+(B[i]-'0');
R22%=M2;
}
//R1, R2 - codificari initiale;
for(i=1; i<N; ++i)
{
pow1*=B1;
pow1%=M1;
pow2*=B2;
pow2%=M2;
}
if(R1 == R11 && R2 == R22)
Sol[++vf]=0;
for(i=N; i<M; ++i)
{
R11=R11-((B[i-N]-'0')*pow1%M1);
R11+=M1;
R11*=B1;
R11+=(B[i]-'0');
R11%=M1;
R22=R22-((B[i-N]-'0')*pow2%M2);
R22+=M2;
R22*=B2;
R22+=(B[i]-'0');
R22%=M2;
if(R1 == R11 && R2 == R22)
Sol[++vf]=i-N+1;
}
g<<vf<<'\n';
for(i=1; i<=min(vf, 1000); ++i)
g<<Sol[i]<<' ';
g<<'\n';
return 0;
}