Saturday, May 08, 2010

Learning C by doing string search






I wanted to be able to confirm that all the characters of a word could be found in a string or not. A friend told me to check out fuzzy string algorithm for this kind of problem. I searched the web, and read a couple of links on the algorithm, however, it appears to be a little different from what I have in mind. So I decided to do "something".

char * name = "janus"
char * searchIn = "jankgopuas";
int count = strlen(name);
int * acc;
int ctemp;
acc = (int *)malloc(count * sizeof(int *));
memset(acc,-1,count);
int position;
for(int i = 0; i < count; ++i){
char * temp = strchr(searchIn,name[i])
position = strlen(searchIn) - strlen(temp);
if temp {
if find(position ,acc){
// find function checks if position is a value is the array already
temp = strchr(searchIn + position , name[i]);
if temp {
acc[i] = strlen(searchIn + position) - strlen(temp);
}
else {
return acc[i];
}
}
acc[i] = position;
}
else{
ctemp = acc[i];
free(acc);
return ctemp;
}
}
ctemp = acc[count - 1];
free(acc);
return ctemp;



Hmm, the above is pretty ugly and I pray you will bear with me. Just learning C and trying out any idea that comes my way.

However, a friend handed this to me.

Scan through name, taking counts of characters to an array
Scan through the search string, decreasing the name character counts
(if over 0)
Scan through the counts, and if any is over 0, no match.

char c[0xff];
memset(c,0,0xff);
int i;
char * str1="foobar";
char * str2="foobababoobar";
char * p;
for (p=str1;*p;p++) c[*p]++;
for (p=str2;*p;p++) if (c[*p]) c[*p]--;
for (i = 0; i < 0xff; i++) if (c[i]) return "no match";
return "match";


There's most likely smarter ways of doing this, could you show me some?








No comments:

Tags

Arduino (1) C (3) Clojure (3) Perl (1) the other side (8) VBA (1)

micro's shared items