Pagini recente » Cod sursa (job #180695) | Cod sursa (job #5040) | Cod sursa (job #20564) | Cod sursa (job #295098) | Cod sursa (job #146589)
Cod sursa(job #146589)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 2000010
char s1[MAX], s2[MAX];
long match[1000], l1, l2, nr_m, pi[MAX];
void prefix()
{
long i, k =0;
pi[0] = 0;
for (i = 2; i<=l1; i++)
{
while ( k > 0 && s1[k+1] != s1[i])
k = pi[k];
if ( s1[k+1] == s1[i] )
k++;
pi[i] = k;
}
}
void solve()
{
long k =0 ;
for ( int i = 1; i<=l2; i++)
{
while ( k > 0 && s1[k+1] != s2[i] )
k = pi[k];
if ( s1[k+1] == s2[i])
k++;
if ( k == l1 )
{
nr_m++;
if (nr_m <= 1000) match[nr_m] = i-l1;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", s1+1);
scanf("%s", s2+1);
l1 = strlen(s1+1);
l2 = strlen(s2+1);
prefix();
solve();
printf("%ld\n", nr_m);
for (int i = 1; i<=nr_m && i<=1000; i++)
printf("%ld ", match[i]);
return 0;
}