Pagini recente » Cod sursa (job #1660203) | Cod sursa (job #2054112) | Monitorul de evaluare | Borderou de evaluare (job #2057854) | Cod sursa (job #806988)
Cod sursa(job #806988)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int Nmax = 2000010;
const int M1 = 1000003;
const int M2 = 1000033;
const int Baza = 73;
char A[Nmax];int N;
char B[Nmax];int M;
int P1,P2;
int H1,H2;
int Act1,Act2,Co;
vector<int> V;
void Count( int i )
{
if ( Act1 == H1 && Act2 == H2 )
{
++Co;
if ( V.size() < 1000 )
V.push_back( i );
}
}
int main()
{
F.getline(A,Nmax,'\n');N=strlen(A);
F.getline(B,Nmax,'\n');M=strlen(B);
P1 = P2 = 1;
for (int i=0;i<N;++i)
{
H1 = ( H1*Baza + A[i] ) % M1;
H2 = ( H2*Baza + A[i] ) % M2;
Act1 = ( Act1*Baza + B[i] ) % M1;
Act2 = ( Act2*Baza + B[i] ) % M2;
}
for (int i=1;i<N;++i)
{
P1 = ( P1 * Baza ) % M1;
P2 = ( P2 * Baza ) % M2;
}
Count( 0 );
for (int i=N;i<M;++i)
{
Act1 = ((Act1 - (B[i-N] * P1) % M1 + M1) * Baza + B[i]) % M1;
Act2 = ((Act2 - (B[i-N] * P2) % M2 + M2) * Baza + B[i]) % M2;
Count( i-N+1 );
}
G<<Co<<'\n';
for (int i=0;i<int(V.size());++i)
G<<V[i]<<' ';
G<<'\n';
}