Discussion :

[kitano902]

Bonjour,

Le problème est le suivant, soit une matrice M:

a b c a a b
a c c a a b
a a b b a c
a d c d a b

Le problème est de trouver l'occurrence d'un mot w dans cette matrice. Le problème revient donc à chercher un mot w dans un texte t, t prenant successivement la valeur des lignes et des colonnes.

Mon idée est donc d'implémenter un algo quelconque, par exemple Knuth-Morris-Pratt en envoyant chaque ligne puis chaque colonne, la difficulté étant de garder les indices bidimensionnels (je pense que le but de l'exercice est cela uniquement). Maintenant, y aurait-il une autre méthode plus intelligente qu'un parcours lignes/colonnes?

Merci pour vos idées

[Mac LAK]

Cela dépend : tes mots peuvent-ils être en diagonale ? Ou écrits suivant n'importe quel parcours (= pas forcément "en ligne") ? A l'endroit et à l'envers ?

[kitano902]

Bonjour,

Je comptais me limiter à une lecture:

ligne: gauche droite
colonne: haut bas
diagonale: haut-gauche puis bas-droite

Si j'ai le temps, peut-être rechercher les inverses.

[Mac LAK]

Si j'ai le temps, peut-être rechercher les inverses.

Pour les inverses, il suffit d'inverser le vecteur extrait et d'appliquer le même algorithme. Cependant, il serait sûrement beaucoup plus efficace de repenser l'algo de base afin de lui permettre de chercher dans n'importe quel sens... Enfin, si tu dois faire un algo de complexité la plus faible possible, du moins.

Sinon, dans le cadre d'une recherche simple, dans un seul sens, tu peux effectivement te contenter d'une extraction de lignes / colonnes / diagonales vers un vecteur, et chercher dans ce vecteur.

Au niveau "finesse", tout dépend si tu dois écrire uniquement un algorithme, ou l'implémenter "peu importe la manière".

Au niveau algo, une méthode comme KMP est adéquate, à toi d'écrire le pseudocode correspondant aux extractions de lignes / colonnes / diagonales, et le pseudocode de recherche.
Au niveau implémentation, il sera sûrement bien plus pratique de transformer le vecteur en chaîne de caractères valide, et d'utiliser une fonction comme strstr (en fonction du langage) pour effectuer cette recherche. L'extraction restera quoi qu'il en soit à ta charge si le langage n'offre pas d'aide à ce niveau.

[kitano902]

ok merci