Pagini recente » Cod sursa (job #614393) | Cod sursa (job #226408) | Cod sursa (job #1405702) | Cod sursa (job #1236608) | Cod sursa (job #932526)
Cod sursa(job #932526)
#include<stdio.h>
#include<string.h>
#define NM 2000000
int main()
{
char a[NM], b[NM];
int pr[NM], i, j, n, m, r, nr = 0,poz[NM];
freopen("strmatch.in", "r", stdin);
scanf("%s%s",a, b);
n = strlen(a), m = strlen(b);
j = 0;
pr[1] = 0;
for(i = 2; i <= n; i++)
{
while ( j>0 && a[j] != a[i-1])
j = pr[j];
if(a[j]==a[i-1])
j++;
pr[i] = j;
//printf("%c %c\n", a[i-1], a[j]);
//printf("%i\n", pr[i]);
}
freopen("strmatch.out", "w", stdout);
r = 0;
for(i = 1; i<=m; i++)
{
while( r>0 && b[i-1] != a[r])
r = pr[r];
if(b[i-1] == a[r])
r++;
if(r == n)
nr++, poz[nr] = i - n+1;
}
printf("%i\n", nr);
for(i = 1; i<=nr;i++)
printf("%i ", poz[i]);
return 0;
}