Sequências numéricas

[askazy]

Dadas duas sequências de n e m elementos binários (0 ou 1), onde n <=m, faça um programa que verifique quantas vezes a primeira sequência aparece na segunda. Exemplo se a primeira por 101 e a segunda 1101010011010 o resultado deve ser 3.

Estou com dificuldade para controlar o laço o que fiz provisoriamente é:

#include <stdio.h>
int main()
{
   int vet[30], vet2[30], i = 0, n, m, j = 0, cont = 0;	    /*vet armazena n e vet2 armazena m, cont conta quantas vezes n aparece em m */
   scanf("%d %d", &n, &m);
   for (i = 0; i < n; i++) {   /*armazena a sequecia n */
    scanf("%d", &vet[i]);
   }
   for (i = 0; i < m; i++) {   /*armazena a sequencia m */
    scanf("%d", &vet2[i]);
   }
   for (i = 0; i < m; i++) {
   }
   printf("O numero de subsequencias eh %d\n", cont);


   return 0;
}

[HappyHippyHippo]

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/naiveStringMatch.htm

[askazy]

Bom fiz algo aqui, o código não é muito bonito, mas acho que funciona:

#include <stdio.h>
int main()
{
   int vet[30], vet2[30], i, n, m, j, b, cont = 0, flag = 0;   /*vet armazena n e vet2 armazena m, cont conta quantas vezes n aparece em m */
   scanf("%d %d", &n, &m);
   for (i = 0; i < n; i++) {   /*armazena a sequecia n */
    scanf("%d", &vet[i]);
   }
   for (i = 0; i < m; i++) {   /*armazena a sequencia m */
    scanf("%d", &vet2[i]);
   }
   for (i = 0; i < m; i++) {
    flag = 0;
    for (j = i, b = 0; b < n; j++, b++) {
	    if (vet2[j] != vet[b])	    /*significa que nao existe subsequencia no intervalo*/
		    flag = 1;
    }
    if (flag == 0)			   /*existe sequencia no intervalo*/
	    cont++;
   }

   printf("O numero de subsequencias eh %d\n", cont);
   return 0;
}

[HappyHippyHippo]

várias soluções:

#include <stdio.h>
#include <string.h>

#define STRING_MAX 30
#define FORMAT_MAX 30

/**
* Pesquisa no número de ocorrência de uma string dentro de outra string
* usando índices
*
* @param n String a ser procurada
* @param m String onde a string irá ser procurada
*
* @return Número de ocorrência
*/
int metodo1(char n[sTRING_MAX], char m[sTRING_MAX]) {
   int i, j, count = 0;

   for (i = 0;                    // começar na primeira posição da string m
        m[i] != '\0';             // até ao fim da string
        ++i) {                    // incrementar uma posição em cada iteração
       for (j = 0;                // iniciar o iterador interno na primeira posição da string a ser procurada
              (n[j] != '\0')      // enquanto houver elementos na string a procurar a serem comparados
           && (m[i + j] != '\0')  // e houver elementos na string a ser pesquisada (não vai o diabo tecelas)
           && (n[j] == m[i + j]); // e os caracteres iterados forem iguais
           ++j)                   // avançar o iterador interno de um caracter
           /* void */;            // não necessita de fazer nada adicional
       count += (n[j] == '\0');   // incrementar uma unidade ao contador de ocorrências caso
                                  // foram encontrados todos os elementos da string a ser procurada
   }

 return count;                    // retornar o número de ocorrência encnotradas
}

/**
* Pesquisa no número de ocorrência de uma string dentro de outra string
* usando ponteiros
*
* @param n String a ser procurada
* @param m String onde a string irá ser procurada
*
* @return Número de ocorrência
*/
int metodo2(char n[sTRING_MAX], char m[sTRING_MAX]) {
   char * i, * j;
   int count = 0;

   for (i = m;                        // começar na primeira posição da string m
        *i != '\0';                   // até ao fim da string
        ++i) {                        // incrementar uma posição em cada iteração
       for (j = n;                    // iniciar o iterador interno na primeira posição da string a ser procurada
               (*j != '\0')           // enquanto houver elementos na string a procurar a serem comparados
            && (*(i + (j-n)) != '\0') // e houver elementos na string a ser pesquisada (não vai o diabo tecelas)
            && (*j == *(i + (j-n)));  // e os caracteres iterados forem iguais
            ++j)                      // avançar o iterador interno de um caracter
           /* void */;                // não necessita de fazer nada adicional
       count += (*j == '\0');         // incrementar uma unidade ao contador de ocorrências caso
                                      // foram encontrados todos os elementos da string a ser procurada
   }

 return count;                        // retornar o número de ocorrência encnotradas
}

/**
* Pesquisa no número de ocorrência de uma string dentro de outra string
* usando a função strstr (string in string)
*
* @param n String a ser procurada
* @param m String onde a string irá ser procurada
*
* @return Número de ocorrência
*/
int metodo3(char n[sTRING_MAX], char m[sTRING_MAX]) {
   int i = 0, count = 0;
   char * pos;

   while ((pos = strstr(&m[i], n)) != NULL) { // enquanto a pesquisa da string a ser procurada for encontrada
                                              // dentro da string m a partir da posição indicada pela variável i
       ++count;                               // incrementar uma unidade ao contador de ocorrências caso
       i = pos - m + 1;                       // passar a procurar outra ocorrẽncia uma posição após a encontrada
   }

 return count;                                // retornar o número de ocorrência encnotradas
}

int main(void)
{
   char format[FORMAT_MAX],
        m[sTRING_MAX],
        n[sTRING_MAX];

   snprintf(format, FORMAT_MAX, "%%%ds %%%ds", STRING_MAX, STRING_MAX);
   scanf(format, n, m);

   printf("O numero de subsequencias no metodo 1 : %d\n", metodo1(n, m));
   printf("O numero de subsequencias no metodo 2 : %d\n", metodo2(n, m));
   printf("O numero de subsequencias no metodo 3 : %d\n", metodo3(n, m));

   return 0;
}