Pagini recente » Cod sursa (job #2229480) | Cod sursa (job #697243) | Cod sursa (job #1795600) | Cod sursa (job #1996823) | Cod sursa (job #1604257)
#include <cstdio>
#include <cstring>
#define NMAX 2000007
using namespace std;
FILE *fin, *fout;
char A[NMAX], B[NMAX];
int pi[NMAX], ans[NMAX], ct, sze1, sze2;
void citire()
{
scanf("%s%s", A + 1, B + 1);
}
void prefix()
{
sze1 = strlen(A + 1);
int k = 0;
pi[1] = 0;
for(int i = 2; i<= sze1; ++i)
{
while(A[k + 1] != A[i] && k) k = pi[k];
if(A[k + 1] == A[i]) ++k;
pi[i] = k;
}
}
void KMP()
{
sze2 = strlen(B + 1);
int k = 0;
for(int i = 1; i<= sze2; ++i)
{
while(k && B[i] != A[k+1]) k = pi[k];
if(B[i] == A[k+1]) ++k;
if(k == sze1)
{
++ct;
if(ct <= 1000)
{
ans[ct] = i - sze1;
}
}
}
}
void afisare()
{
printf("%d\n", ct);
if(ct <= 1000) for(int i = 1; i<= ct; ++i) printf("%d ", ans[i]);
else for(int i = 1; i<= 1000; ++i) printf("%d ", ans[i]);
printf("\n");
}
int main()
{
fin = freopen("strmatch.in", "r", stdin);
fout = freopen("strmatch.out", "w", stdout);
citire();
prefix();
KMP();
afisare();
fclose(fin);
fclose(fout);
return 0;
}