Pagini recente » Cod sursa (job #2109744) | Cod sursa (job #2835929) | Cod sursa (job #2205583) | Cod sursa (job #2114259) | Cod sursa (job #143857)
Cod sursa(job #143857)
# include <stdio.h>
# include <cstring>
using namespace std;
# define input "strmatch.in"
# define output "strmatch.out"
# define max 2000002
char a[max],b[max];
int ant[max],n,m,i,q,res[1001],lr;
int main()
{
freopen(input, "r", stdin);
freopen(output, "w",stdout);
scanf("%s%s",a,b);
n = strlen(a);
m = strlen(b);
for(i=n;i;i--)
a[i] = a[i-1];
a[0] = ' ';
for(i=m;i;i--)
b[i] = b[i-1];
b[0] = ' ';
q = 0;
for(i = 2;i<=n;i++)
{
while(a[q+1]!=a[i] && q)
q = ant[q];
if(a[i] == a[q+1])
q++;
ant[i] = q;
}
q = 0;
lr=0;
for(i=1;i<=m;i++)
{
while(q > 0 && b[i] != a[q+1])
q = ant[q];
if(a[q+1] == b[i])
q = q+1;
if(q == n)
{
q = ant[q];
lr++;
if(lr <= 1000)
res[lr] = i - n;
}
}
printf("%d\n",lr);
for(i=1;i<=(lr > 1000 ? 1000 : lr);i++)
printf("%d ",res[i]);
return 0;
}