Pagini recente » Cod sursa (job #178657) | Cod sursa (job #2643082) | Cod sursa (job #1743660) | Cod sursa (job #2726055) | Cod sursa (job #2063230)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20000005
using namespace std;
char a[N], b[N];
int poz[N], sol[1005], n, m, l;
void prefix()
{
int j=0;
for(int i=2;i<=n;i++)
{
while(j && a[j+1]!=a[i])
j=poz[j];
if(a[j+1]==a[i])
j++;
poz[i]=j;
}
}
void cautare()
{
int j=0;
for(int i=1;i<=m;i++)
{
while(j && a[j+1]!=b[i])
j=poz[j];
if(a[j+1]==b[i])
j++;
if(j==n)
{
j=poz[n];
if((l+1)<=1000)
sol[++l]=i-n;
}
}
}
void afisare()
{
printf("%d\n", l);
for(int i=1;i<=min(l, 1000);i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a+1, N, stdin);
fgets(b+1, N, stdin);
n=strlen(a+1)-1;
m=strlen(b+1)-1;
prefix();
// for(int i=1;i<=n;i++)
// printf("%d ", poz[i]);
cautare();
afisare();
return 0;
}