Mai intai trebuie sa te autentifici.
Cod sursa(job #205789)
Utilizator | Data | 2 septembrie 2008 22:48:41 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1 kb |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 2000002
#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();
}