Pagini recente » Cod sursa (job #2180616) | Cod sursa (job #2169965) | Cod sursa (job #101304) | Cod sursa (job #2250510) | Cod sursa (job #898017)
Cod sursa(job #898017)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int pi[2100000],n,m,i,nr,poz[1100],q;
char a[2100000],b[2100000];
void piu ()
{
int i,q;
q = 0; pi[0] = 0;
for (i=2; i<=n; i++)
{
while (q && a[i] != a[q+1])
q = pi[q];
if (a[i] == a[q+1]) q++;
pi[i] = q;
}
return;
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
n = strlen(a+1);
m = strlen(b+1);
piu();
nr = 0;
for (i=1; i<=m; i++)
{
while (q && a[q+1] != b[i]) q = pi[q];
if (a[q+1] == b[i]) q++;
if (q == n)
{
nr++;
if (nr<=1000)
{
poz[nr] = i - n ;
}
}
}
printf ("%d\n",nr);
for (i=1; i<=min(nr,1000); i++) printf ("%d ",poz[i]);
printf ("\n");
return 0;
}