pourquoi ne changeons-nous pas de cette façon?

Tout en étudiant algorithme Knuth-Morris-Pratt pour une chaîne:pourquoi ne changeons-nous pas de cette façon?

ABC ABCDAB ABCDAB

pour un motif:

ABCDABD

Je suis coincé sur une seule étape. Je vais mettre en évidence l'étape où je suis actuellement coincé.

ABC ABCDAB ABCDAB 
ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
     ABCDABD--------------------(WHY THIS ?)

Je ne comprends pas l'étape ci-dessus. Je m'attends à ce que l'étape ci-dessus soit:

ABC ABCDAB ABCDAB 
      ABCDABD

Veuillez expliquer la logique/raison de l'étape 'correcte'.

Source

2012-11-01 saplingPro

Le deuxième AB dans le modèle correspond, donc nous décalons de telle sorte que le premier AB est maintenant où le second était. Pourquoi pensez-vous que nous pouvons aller plus loin? –

@ n.m. pouvez-vous me dire les critères pour rechercher en travaillant avec _knuth morris_ algo. Je ne comprends pas complètement, même si j'ai essayé de lire le [article wikipedia] (http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) – saplingPro

Lorsque '' Comparer avec 'D', il trouve une discordance. Et cet algorithme 'se souvient' que le précédent 'AB' est comparé, il doit donc vérifier si le caractère non concordant est 'C'.

L'idée de la méthode KMP est expliquée dans le livre 'Introduction to Algorithms'. Il est très similaire à la méthode de la machine d'état infinie, ce qui peut vous aider à le comprendre.

Source

2012-11-02 04:12:58 Richard

pourquoi ne changeons-nous pas de cette façon?

Répondre

Questions connexes