Pagini recente » Cod sursa (job #3201325) | Cod sursa (job #1350524) | Cod sursa (job #1343926) | Cod sursa (job #1062098) | Cod sursa (job #539916)
Cod sursa(job #539916)
#include <stdio.h>
#include <string.h>
#define N 2000001
#define minim(a, b) ( (a < b) ? a : b)
using namespace std;
char a[N], b[N];
int pi[N], pos[1002], n, m, nr;
void prefix()
{
int i, q=0;
for(i=1, pi[0] = 0; i<m; i++)
{
while(q && a[q] != a[i])
q = pi[q-1];
if(a[i] == a[q])
q++;
pi[i] = q;
}
}
int main()
{
int i, q=0, nr=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a);
gets(b);
m = strlen(a);
n = strlen(b);
prefix();
//potrivire;
for(i=0; i<n; i++)
{
while(q && a[q] != b[i])
q = pi[q-1];
if(a[q] == b[i])
q++;
if(q == m)
{
q = pi[m-1];
++nr;
if(nr <= 1000)
pos[nr] = i - m + 1;
}
}
printf("%d\n", nr);
for(i=1; i <= minim(nr, 1000); i++)
printf("%d ", pos[i]);
printf("\n");
return 0;
}