Pagini recente » Cod sursa (job #2335042) | Cod sursa (job #3293488) | Cod sursa (job #8772) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 181 | Cod sursa (job #795018)
Cod sursa(job #795018)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
char A[NMAX],B[NMAX];
int sol[NMAX],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)
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;
}