Pagini recente » Cod sursa (job #2450085) | Cod sursa (job #3294059) | Cod sursa (job #3286138) | Cod sursa (job #541611) | Cod sursa (job #1963991)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define NMAX (2000000 + 7)
#define pb push_back
using namespace std;
char A[NMAX], B[NMAX];
int phi[NMAX], szeA, szeB, ct;
vector <int> sol;
inline void prefix()
{
phi[1] = 0;
int k = 0;
for(int i = 2; i<= szeA; ++i)
{
while(A[k+1] != A[i] && k) k = phi[k];
if(A[k+1] == A[i]) ++k;
phi[i] = k;
}
}
inline void stringMatch()
{
int k = 0;
for(int i = 1; i<= szeB; ++i)
{
while(A[k+1] != B[i] && k) k = phi[k];
if(A[k+1] == B[i]) ++k;
if(k == szeA)
{
++ct;
if(ct <= 1000)
{
sol.pb(i-szeA);
}
}
}
}
inline void afisare()
{
printf("%d\n", ct);
for(int i = 0; i< min(1000, ct); ++i) printf("%d ", sol[i]);
printf("\n");
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%s\n%s\n", A+1, B+1);
szeA = strlen(A+1);
szeB = strlen(B+1);
prefix();
stringMatch();
afisare();
return 0;
}