Pagini recente » Cod sursa (job #1811412) | Cod sursa (job #3272669) | Cod sursa (job #347685) | Cod sursa (job #2223926) | Cod sursa (job #205781)
Cod sursa(job #205781)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 2000000
#define min(a,b) (a) < (b) ? (a) : (b)
char T[NMAX],P[NMAX];
int offset[NMAX];
void citire()
{
freopen("strmatch.in","rt",stdin);
scanf("%s %s",P,T);
}
void afis(int match[] ,int num)
{
freopen("strmatch.out","wt",stdout);
printf("%d\n",num);
num = min(num,1000);
for(int i = 0; i < num ; ++i)
printf("%d ",match[i]);
}
void kmp() //knuth morris pratt O(N+M)
{
int N = strlen(T),M = strlen(P);
for(int i = 1, k = 0; i < M; ++i)
{
while( offset[k] > 0 & P[k] != P[i])
k = offset[k] - 1;
if(P[i] == P[k]) ++k;
offset[i] = k;
}
int match[1000],num = 0;
for(int j = 0,i = 0; i < N ; ++i)
{
while(j > 0 & T[i] != P[j]) j = offset[j - 1];
if(T[i] == P[j]) ++j;
if(j==M)
{
match[num++] = i - M + 1 , j = offset[j - 1];
if(num == 1000) break;
}
}
afis(match,num);
}
int main()
{
citire();
kmp();
}