Pagini recente » Cod sursa (job #3147088) | Cod sursa (job #1302465) | Cod sursa (job #3186510) | Cod sursa (job #3001227) | Cod sursa (job #1969822)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000000;
int n, m;
char a[5 + NMAX];
char b[5 + NMAX];
int pi[1 + NMAX];
void prefix()
{
int k = 0;
for(int i = 2; i <= n; i++)
{
while(k > 0 && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
k++;
pi[i] = k;
}
}
int ct;
int pos[1001];
void solve()
{
int k = 0;
for(int i = 1; i <= m; i++)
{
while(k > 0 && a[k + 1] != b[i])
k = pi[k];
if(a[k + 1] == b[i])
k++;
if(k == n)
{
ct++;
if(ct <= 1000)
{
pos[ct] = i - n;
}
k = pi[k];
}
}
}
void output()
{
printf("%d\n", ct);
int lim = min(ct, 1000);
for(int i = 1; i <= lim; i++)
{
printf("%d ", pos[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a + 1, b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
prefix();
solve();
output();
return 0;
}