Pagini recente » Cod sursa (job #3255959) | Cod sursa (job #2724397) | Cod sursa (job #1582530) | Cod sursa (job #1589973) | Cod sursa (job #2480801)
#define NMAX 2000010
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char a[NMAX], b[NMAX];
int P[NMAX], o[1005];
int n, m, nro;
/// caut a in b
void formPrefix()
{
int i=1, j = 0;
P[0] = -1;
while(i<=n)
{
while(j > 0 && a[i] != a[j])
j = P[j];
P[i] = j;
i++, j++;
}
}
void kmp()
{
int i=1, j=1;
while(i <= m)
{
while(j > 0 && b[i] != a[j])
j = P[j-1]+1;
i++;
j++;
if(j == n+1){
j = P[j-1]+1;
if(nro < 1000)
o[nro++] = i-n-1;
}
}
}
void afis()
{
printf("%d\n", nro);
for(int i=0; i<nro; ++i)
printf("%d ", o[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", (a+1), (b+1));
n = strlen(a+1);
m = strlen(b+1);
formPrefix();
kmp();
afis();
return 0;
}