Pagini recente » Cod sursa (job #2021658) | Cod sursa (job #728979) | Cod sursa (job #1285672) | Rating Petridean Ovidiu (ulltrass) | Cod sursa (job #2297755)
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
char a[2000005], b[2000005];
int n, m;
int prefix[2000005];
int v[1005];
void citire()
{
scanf("%s\n%s", a+1, b+1);
n = strlen(a+1);
m = strlen(b+1);
}
void calculPrefix()
{
int k = 0;
prefix[1] = 0;
for(int i = 2; i<=n; i++)
{
while(k>0 && a[i]!=a[k+1])
{
k = prefix[k];
}
if(a[i] == a[k+1])
{
k++;
}
prefix[i] = k;
}
}
void potrivire()
{
int k = 0;
for(int i = 1; i<=m; i++)
{
while(k>0 && a[k+1] != b[i])
{
k = prefix[k];
}
if(a[k+1] == b[i])
{
k++;
}
if(k == n)
{
if(v[0]<=1000)
v[v[0]++] = i-n;
else
v[0]++;
}
}
}
void afisare()
{
printf("%d\n", v[0]-1);
for(int i = 1; i<v[0] && i<=1000; i++)
{
printf("%d ", v[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
v[0] = 1;
calculPrefix();
potrivire();
afisare();
return 0;
}