Pagini recente » Cod sursa (job #1968139) | Cod sursa (job #217018) | Cod sursa (job #1291106) | Cod sursa (job #2547005) | Cod sursa (job #878144)
Cod sursa(job #878144)
#include <cstdio>
#include <cstring>
#include <assert.h>
# define NMAX 2000002
void computePrefixFunction(char *a, int *pi, int m){
pi[1] = 0;
int k = 0;
for(int q = 2; q <= m; ++q){
while (k > 0 && a[k + 1] != a[q]){
k = pi[k];
}
if (a[k + 1] == a[q]){
++k;
}
pi[q] = k;
}
}
int pi[NMAX];
char a[NMAX+1], b[NMAX+1];
int matches[1024];
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int m, n;
a[0] = ' ', b[0] = ' ';
fgets(a + 1, NMAX, stdin);
fgets(b + 1, NMAX, stdin);
// search a substring into b
// printf("%s", a);
// printf("%s", b);
m = strlen(a) - 2; // get rid of newline and space
n = strlen(b) - 2; // get rid of newline and space
computePrefixFunction(a, pi, m);
//for(int i = 1; i <=m; i++){
// printf("%d ", pi[i]);
//}
//putchar('\n');
// kmp
int matchCount = 0;
int q = 0; // number of characters matched
for(int i = 1; i <= n; i++){
while ( q > 0 && a[q + 1] != b[i]){
// next character does not match
q = pi[q];
}
if (a[q + 1] == b[i])
++q;
if (q == m){
if(matchCount < 1000)
matches[matchCount++] = i - m;
q = pi[q]; // look for next mat
}
}
// print matches
assert(matchCount<=1000);
printf("%d\n", matchCount);
for(int i = 0; i < matchCount; ++i){
printf("%d ", matches[i]);
}
putchar('\n');
return 0;
}