Pagini recente » Cod sursa (job #3288226) | Cod sursa (job #1924548) | Cod sursa (job #1890570) | Cod sursa (job #1057539) | Cod sursa (job #160652)
Cod sursa(job #160652)
//Potrivirea sirurilor - KMP
#include <stdio.h>
#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"
#define MAX 2000001
#define AMAX 1001
char A[MAX], B[MAX];
int T[MAX], poz[AMAX];
int nr;
void prefix()
{
int i, k = -1;
T[0] = -1;
for(i = 1; A[i]; ++i)
{
while(k >= 0 && A[i] != A[k+1])
k = T[k];
if(A[i] == A[k+1]) ++k;
T[i] = k;
}
}
void potrivire()
{
int i, k = -1;
for(i = 0; B[i]; ++i)
{
while(k >= 0 && B[i] != A[k+1])
k = T[k];
if(B[i] == A[k+1]) ++k;
if(k>0 && !A[k+1])
{
if(nr < 1000) poz[++nr] = i-k;
if(nr == 1000) return;
}
}
}
void afis()
{
int i;
printf("%d\n", nr);
if(nr)
{
for(i = 1; i < nr; ++i)
printf("%d ", poz[i]);
printf("%d\n", poz[nr]);
}
}
int main()
{
freopen(INPUT, "r", stdin);
freopen(OUTPUT, "w", stdout);
scanf("%s\n", A);
scanf("%s\n", B);
prefix();
potrivire();
afis();
return 0;
}