Pagini recente » Cod sursa (job #621240) | Cod sursa (job #36162) | Cod sursa (job #141998) | Cod sursa (job #447170) | Cod sursa (job #1434686)
#include <cstring>
#include <cstdio>
#define lengmax 2000005
#define maxx 1000
char x[lengmax], y[lengmax];
int l[lengmax], apar[lengmax], p;
void build_lv()
{
int k = 0;
int n = strlen(x) - 1;
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 k = 0;
int n = strlen(x) - 1;
int m = strlen(y) - 1;
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) apar[++p] = i - n;
}
printf("%d\n", p);
for(int i = 1; i<=minim(1000, p); i++)
printf("%d ", apar[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(x + 1);
x[0] = ' ';
gets(y + 1);
y[0] = ' ';
build_lv();
solve();
}