Search between two vectors

1

I am doing a project for a course, but I have some problems. The problem to overcome is, in a text file, consisting of id \t and a sequence of 2048 fixed '0' and '1' , insert a sequence and search for the most similar elements.

My code has only one search algorithm, but that does not solve the problem, because if the string entered is not the same as the one in the file, it does 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;

}
    
asked by anonymous 02.06.2017 / 13:12

1 answer

0

This problem is very similar to the "Longest prefix match", famous for IPv4 and IPv6 routing protocols.

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

Longest_Prefix_Match (IN)

  • N = 0
  • S = first entry
  • M = how many equal bits are in the beginning of S and IN
  • If M > N

    a. OUT = S

    b. N = M

  • If you have more entries

    a. S = next entry

    b. Go back to line 3.

  • return OUT
  • An error that 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;
    
        
    14.08.2017 / 19:48