Pagini recente » Cod sursa (job #692294) | Cod sursa (job #836017) | Cod sursa (job #917041) | Cod sursa (job #3266014) | Cod sursa (job #795021)
Cod sursa(job #795021)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define LMAX 1005
char A[NMAX],B[NMAX];
int sol[LMAX],r;
int n,m,pi[NMAX];
inline int check(char x)
{
return (x>='0' && x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z') ;
}
void read()
{
fgets(A+1,NMAX,stdin);
fgets(B+1,NMAX,stdin);
while (check(A[n+1])) n++;
while (check(B[m+1])) m++;
}
void precompute()
{
int i,q=0;
for (i=2; i<=n; i++)
{
while (q && A[q+1]!=A[i])
q=pi[q];
if (A[q+1]==A[i])
q++;
pi[i]=q;
}
}
void solve()
{
int i,q=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)
{
if (r<1000)
sol[++r]=i-n+1;
q=pi[q];
}
}
printf("%d\n",r);
for (i=1; i<=r; i++)
printf("%d ",sol[i]-1);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
precompute();
solve();
return 0;
}