Pagini recente » Cod sursa (job #241763) | Cod sursa (job #1982887) | Cod sursa (job #1801170) | Cod sursa (job #1767129) | Cod sursa (job #2063235)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000005
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];
l++;
if(l<=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;
}