Pagini recente » Cod sursa (job #1268309) | Cod sursa (job #433212) | Cod sursa (job #2383138) | Borderou de evaluare (job #2772060) | Cod sursa (job #1468722)
#include<stdio.h>
#include<string.h>
#define MAX 2000000
char A[MAX],B[MAX];
int pi[MAX],sol[1005],n,m,total;
void buildPrefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= m; i++){
while ( q && A[q+1] != A[i] )
q = pi[q];
if (A[q+1] == A[i]){
q++;
}
pi[i] = q;
}
}
void solve()
{
int q = 0,i;
for ( i = 1; i <= n; ++i)
{
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == m)
{
q = pi[m];
if(total < 1000)
sol[total] = i-m;
total++;
}
}
}
void show()
{
int i;
printf("%d\n",total);
for( i = 0; i < (total < 1000 ? total : 1000); i++)
printf("%d ",sol[i]);
}
int main()
{
freopen("potrivire.in","r",stdin);
freopen("potrivire.out","w",stdout);
scanf("%s %s",&A,&B);
m = strlen(A+1);
n = strlen(B+1);
if(m > n){
printf( "Subsirul %s nu se gaseste in sirul %s \n",A,B );
return 0;
}
buildPrefix();
solve();
show();
fclose(stdin);
fclose(stdout);
return 0;
}