Pagini recente » Profil ELHoria | Monitorul de evaluare | Cod sursa (job #1441366) | Cod sursa (job #2845540) | Cod sursa (job #1361544)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream is("strmatch.in");
ofstream os("strmatch.out");
char A[2000002], B[2000002];
int N, M, k;
int PI[2000002];
int F;
vector <int> Sol;
void BuildPI()
{
k = 0;
for ( int i = 2; i <= N; ++i)
{
while ( k > 0 && A[k+1] != A[i] )
k = PI[k];
if ( A[k+1] == A[i] )
k++;
PI[i] = k;
}
}
void MainEvent()
{
k = 0;
for ( int i = 1; i <= M; ++i)
{
while ( k > 0 && A[k+1] != B[i] )
k = PI[k];
if ( A[k+1] == B[i] )
k++;
if ( k == N )
Sol.push_back(i-N);
}
}
int main()
{
is >> A+1 >> B+1;
N = strlen(A+1);
M = strlen(B+1);
BuildPI();
MainEvent();
os << Sol.size() << '\n';
F = min((int)Sol.size(),1000);
for ( int i = 0; i < Sol.size(); ++i )
os << Sol[i] << " ";
}