Pagini recente » Cod sursa (job #1904050) | Cod sursa (job #2702954) | Cod sursa (job #1507650) | Cod sursa (job #619159) | Cod sursa (job #1105237)
#include <iostream>
#include <cstdio>
#include <cstring>
#define Nmax 2000005
using namespace std;
char a[Nmax],b[Nmax];
int n,m;
int pi[Nmax];
int aparitii;
int pos[Nmax];
void citire()
{
scanf("%s\n",a+1);
scanf("%s\n",b+1);
a[0] = ' ';
b[0] = ' ';
m = strlen(a);
n = strlen(b);
m--;
n--;
}
void make_prefix()
{
int q = 0;
pi[1] = 0;
for (int i=2; i<=m; i++)
{
while(q && a[q+1] != a[i])
q = pi[q];
if (a[q+1] == a[i])
q++;
pi[i] = q;
}
}
void afisare()
{
printf("%d\n",aparitii);
for (int i=1; i<=aparitii; i++)
printf("%d ",pos[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
make_prefix();
int q = 0;
for (int i=1; i<=n; i++)
{
while(q && a[q+1] != b[i])
q = pi[q];
if (a[q+1] == b[i])
q++;
if (q == m)
{
aparitii++;
q = pi[m];
if (aparitii <= 1000)
pos[aparitii] = i - m;
}
}
afisare();
return 0;
}