Pagini recente » Cod sursa (job #1177753) | Cod sursa (job #169757) | Cod sursa (job #2520) | Cod sursa (job #2794754) | Cod sursa (job #420186)
Cod sursa(job #420186)
// Catalin Balan
// Thu Mar 18 16:40:00 EET 2010
// KMP
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define NMAX 2000015
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
char A[NMAX], B[NMAX];
int pref[NMAX];
int rez[1024];
int N,M;
void makePrefix()
{
pref[1] = 0;
for (int i = 2, p = 0; i <= N; ++i)
{
while (p && A[i] != A[p+1]) p = pref[p];
if (A[i] == A[p+1]) ++p;
pref[i] = p;
}
}
int main(int argv, char ** argc)
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
gets(A);
gets(B);
N = strlen(A);
M = strlen(B);
for (int i = N; i; --i) A[i] = A[i-1];
for (int i = M; i; --i) B[i] = B[i-1];
A[0] = B[0] = ' ';
A[N+1] = 0;
makePrefix();
int cate = 0;
for (int i = 1, p = 0; i <= M; ++i)
{
while (p && B[i] != A[p+1]) p = pref[p];
if ( B[i] == A[p+1]) ++p;
if (p == N)
{
p = pref[p];
++cate;
if (cate <= 1000)
{
rez[cate] = i-N;
}
}
}
printf("%d\n", cate);
if (cate > 1000) cate = 1000;
for (int i = 1; i <= cate; ++i)
{
printf("%d ", rez[i]);
}
return EXIT_SUCCESS;
}