Naive Algorithm Program in C

Hello Yira,

If the algorithm is not given, you must determine it before you start coding in C.

This page can certainly help you: https://www.irif.fr/~carton//Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/

However, you will need to check your course materials to confirm whether this algorithm has an "inner loop," and does not have a "fast loop" or a "sentinel." These are concepts that should have been explained to you by the person who drafted the assignment (your teacher?).

Regarding your C code, you should seriously review your basics.

I think you are confusing the syntax for declaring a function with that of declaring an array with your x and y, and the prototype of your function does not make sense to me.

Here is a skeleton of C code featuring a reasonable prototype for this function, and allowing you to test the implementation of your algorithm.

I would like to quote a passage from Mr. Olivier CARTON's course, located at the previously mentioned address, in the comment of the function

int premiere_occurrence(char * motif, char * texte)

.

#include <stdio.h>

/**
 * premiere_occurrence - naive text search
 *
 * motif : pattern to search for
 * texte : text where the pattern is searched
 *
 * returns :
 * -1 if the pattern is not present
 * or the position of the first occurrence
 */
int premiere_occurrence(char * motif, char * texte)
{
 /*
 * For each possible position of the pattern in the text,
 * we test whether this position is an occurrence of the pattern.
 * This test is performed by comparing the characters of the
 * pattern with the characters of the text from left to right.
 * If all characters of the pattern are equal to the
 * characters of the text at the corresponding positions,
 * an occurrence has been found and the position of this
 * occurrence is returned. Otherwise, the search continues
 * by moving to the next position.
 */
}

int main(void)
{
 char * motif = "Toto";
 char * texte = "Le professeur demande à Toto :\n"
 "- Toto, 3 et 3 ça fait quoi ?\n"
 "- Match nul monsieur !";
 int position;

 position = premiere_occurrence(motif, texte);

 if (position == -1)
 {
 printf("motif [%s] non trouvé dans le texte\n", motif);
 }
 else
 {
 printf("le motif [%s] a été trouvé en position %d\n", 
 motif, position);
 /* the correct result is 25 */
 }

 return 0;
}

It's your turn to play :-)


Dal

If you want to count the number of occurrences, in principle, it "just" requires modifying the algorithm so that instead of returning the position of the first occurrence, it increments a count of occurrences and continues searching through the rest of the text string, then returns the count when the end of the text string is reached.

That said, I don't know much about DNA molecules.

If you have "CGCAACAT", and you search for "ACAT", you will find it, and if you search for "CGCAA" you will find it too, and I don't know if the fact that they share a character is important to you, especially if your search needs to indicate the number of occurrences of "ACAT" and "CGCAA".


Dal