Pagini recente » Cod sursa (job #1038631) | Cod sursa (job #2958072) | Cod sursa (job #1653736) | Cod sursa (job #1515352) | Cod sursa (job #1374236)
#include <cstdio>
#include <cstring>
#define Nmax 2000005
#define nmin 1005
using namespace std;
char x[Nmax], y[Nmax];
int l[Nmax], ap[Nmax], p;
void build_l()
{
int n = strlen(x) - 1;
int k = 0;
l[1] = 0;
for(int i = 2; i<=n; i++)
{
while(x[i] != x[k + 1] && k > 0)
k = l[k];
if(x[i] == x[k + 1]) k ++;
l[i] = k;
}
}
inline int minim(int a, int b)
{
return a > b? b : a;
}
void solve()
{
int n = strlen(x) - 1, m = strlen(y) - 1;
int k = 0;
for(int i = 1; i<=m; i++)
{
while(y[i] != x[k + 1] && k > 0)
k = l[k];
if(y[i] == x[k + 1]) k ++;
if(k == n) ap[++ p] = i - n ;
}
printf("%d\n", p);
for(int i = 1; i<=minim(p, 1000); ++i)
printf("%d ", ap[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(x + 1);
x[0] = ' ';
gets(y + 1);
y[0] = ' ';
build_l();
solve();
}