Pagini recente » Cod sursa (job #1768681) | Cod sursa (job #1806598) | Cod sursa (job #698809) | Cod sursa (job #1325206) | Cod sursa (job #1248755)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#define NMAX 2000005
using namespace std;
void computeLPSArray(char* pat, long M, long* lps) {
long len = 0, i = 1;
lps[0] = 0;
while(i < M) {
if(pat[i] == pat[len]) {
lps[i++] = ++len;
} else {
if(len != 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
}
}
void KMPSearch(char* pat, char* txt) {
long M = strlen(pat);
long N = strlen(txt);
long* lps = (long*) malloc(sizeof(long) * M);
long sol[1000];
long i, j, k = 0;
computeLPSArray(pat, M, lps);
while(i < N) {
if(pat[j] == txt[i]) {
i++; j++;
}
if(j == M) {
if(k < 1000) {
sol[k] = i - j;
}
k++;
j = lps[j - 1];
} else if(pat[j] != txt[i]) {
if(j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
printf("%ld\n", k);
if(k > 1000) k = 1000;
for(i = 0; i < k; i++) {
printf("%ld ", sol[i]);
}
printf("\n");
free(lps);
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char pat[NMAX], txt[NMAX];
scanf("%s%s", pat, txt);
KMPSearch(pat, txt);
return 0;
}