Search between two vectors

Question

I’m doing a project for a class, but I’m having some problems. The problem to overcome is, in a text file, composed of a id \t and a fixed 2048 sequence '0' and '1', insert a sequence and find the most similar elements.

My code has only one search algorithm, but it does not solve the problem, because if the entered sequence is not the same as the one in the file, you will not find a macth.

#include <stdio.h>
#include <stdlib.h>
//#include "ler.h"

int pesquisa(){

    int n,*s,i,*c,a,j;
    FILE *fp;
    int *v;
    fp = fopen("tesste.txt", "r");
    v=(int*)malloc(sizeof(int));

    while(!feof(fp)){
        fscanf(fp,"\t%d",&v);
    }

    //printf("Valor n %d\n",v);
    //scanf("%d",&n);

    s=(int*)malloc(sizeof(int));
    c=(int*)malloc(sizeof(int));

    printf("Introduza a sequencia e tamanho da seq\n");

    scanf("%d",&a);

    for(j=0;j<a;j++){
        scanf("%d\n",&s[j]);
    }

    for(i=0;i<a;i++){
        if(s[i]==v[i])
            //printf("%d",a);
            //c[i]=s[i];
            return (1);
         else
            return (0);
    }

    // printf("%d",c);

    free(v);
    free(s);
    free(c);

    fclose(fp);

    return 0;

}

Answer 1

This problem is very similar to the "Longest prefix match", famous because of the Ipv4 and Ipv6 routing protocols.

The brute force algorithm for this problem would be as follows:

Longest_prefix_match(IN)

1. N = 0
2. S = first entry
3. M = how many equal bits you have at the beginning of S and IN

4. If M > N

   a. OUT = S

   b. N = M

5. If you have more entries

   a. S = next entry

   b. Back to line 3.

6. Return OUT

One mistake you are making is that you do not compare all sequences, but return 1 if the first bit of the sequences are equal and 0 otherwise.

int count = 0;
for(i=0;i<a;i++){
    if(s[i]==v[i])
        count++;
     else
         break;
    }

...
return count;