"Pilcrow" <Pilcrow6@gmail.comwrote in message
news:9p5di4lgheigdmmic41rmo79dh2i0eqkgs@4ax.com...
Quote:
This problem was raised in comp.lang.perl.misc, and the poster was
concerned, among other things, by the speed of execution.
Since C is faster than perl, I wonder how a C coder would solve it?
>
Given a *very* long string, A, and a shorter string, B, extract all
substrings of A that differ from B in at most N positions.
>
For example:
N = 2
A = 'abcdefaacdefxbcxfaaabcdefaaaacdxf'
B = 'abcdef'
the substrings are 'abcdef' at offsets 0 & 19, 'aacdef' at offset 6, and
'aacdxf' at offset 27.
|
Here's how /I/ did, as an occasional C coder; this assumes substrings can
overlap:
#include <stdio.h>
#include <string.h>
int main(void) {
char *a="abcdefaacdefxbcxfaaabcdefaaaacdxf";
char *b="abcdef";
int n=2;
int blen;
int i,j,k,c;
blen=strlen(b);
k=strlen(a)-blen+1;
for (i=0; i<k; ++i) {
/* Compare substring a[i]..a[i+blen-1] with b*/
c=0;
for (j=0; j<blen; ++j)
if (a[i+j]!=b[j]){
++c;
if (c>n) break;
}
if (c<=n) {
printf("Offset: %d Substring: ",i);
for (j=0; j<blen; ++j) printf("%c",a[i+j]);
puts("");
}
}
}
--
Bartc
