Pagini recente » Cod sursa (job #1920966) | Cod sursa (job #2562479) | Cod sursa (job #724005) | Cod sursa (job #1324924) | Cod sursa (job #2028061)
#include <bits/stdc++.h>
using namespace std;
char a[2000005];
char b[2000005];
int d[2000005];
int nrsol = -1, sol[1000];
int la, lb;
void precalc()
{
int q = -1;
d[0] = -1;
for(int i = 1; i < la; i++)
{
while(q != -1 && a[q + 1] != a[i])
q = d[q];
if(a[q + 1] == a[i])
q++;
d[i] = q;
}
}
void solve()
{
precalc();
int q = -1;
for(int i = 0; i < lb; i++)
{
while(q != -1 && b[i] != a[q + 1])
q = d[q];
if(b[i] == a[q + 1])
q++;
if(q == la - 1)
{
++nrsol;
if(nrsol < 1000)
sol[nrsol] = i - la + 1;
q = d[q];
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a, b);
la = strlen(a);
lb = strlen(b);
solve();
nrsol++;
printf("%d\n", nrsol);
int k = min(1000, nrsol);
for(int i = 0; i < k; i++)
printf("%d ", sol[i]);
return 0;
}