Comment implémenter l'algorithme KMP en C#

Comment implémenter l'algorithme KMP en C#

L'algorithme KMP (Knuth-Morris-Pratt) est un algorithme de correspondance de chaînes efficace utilisé pour trouver la position des chaînes de modèle dans les chaînes de texte. Son idée principale est d’utiliser les informations partielles qui ont été mises en correspondance pour éviter des comparaisons inutiles.

La clé pour implémenter l'algorithme KMP est de créer une table de correspondance partielle (Partial Match Table), également appelée tableau suivant. Ce tableau enregistre la longueur de la sous-chaîne de suffixe correspondante la plus longue de chaque sous-chaîne de préfixe dans la chaîne de modèle.

Voici les étapes spécifiques et des exemples de code pour implémenter l'algorithme KMP en C# :

Étape 1 : Créer une table de correspondance partielle

1. Définissez ensuite un tableau d'entiers avec une taille égale à la longueur de la chaîne de modèle et initialisez suivant[0] = -1 .
2. Définissez deux pointeurs i et j, avec respectivement les valeurs initiales 0 et -1.
3. Déterminez si i atteint la fin de la chaîne de motif, sinon, effectuez les étapes suivantes :
   a. Si j est égal à -1 ou si le caractère actuel est égal au caractère correspondant au pointeur j, alors i et j le feront. être déplacé vers l'arrière en même temps, et next[i ] = j.
   b. Sinon, déplacez le pointeur j vers la position next[j] et continuez la correspondance.
4. Renvoyez ensuite la table de correspondance partielle construite.

Voici le code permettant de mettre en œuvre les étapes ci-dessus :

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

Étape 2 : Utilisez une table de correspondance partielle pour la correspondance

1. Définissez deux pointeurs i et j, pointant vers les positions de départ de la chaîne de texte et du motif chaîne respectivement.
2. Déterminez si i et j ont atteint la fin. Sinon, effectuez les étapes suivantes :
   a. Si j est égal à -1 ou si le caractère actuel est égal au caractère correspondant au pointeur j, alors i et j se déplaceront. en arrière en même temps.
   b. Sinon, déplacez le pointeur j vers la position next[j] et continuez la correspondance.
3. Si le pointeur j pointe vers la fin de la chaîne de modèle, cela signifie que la correspondance est réussie et l'index de la position de départ dans la chaîne de texte est renvoyé.
4. Si le match échoue, -1 sera renvoyé.

Voici le code expliquant comment implémenter les étapes ci-dessus :

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

En appelant la méthode KMP et en transmettant la chaîne de texte et la chaîne de modèle, vous pouvez obtenir le résultat correspondant.

Ci-dessus sont les étapes et les exemples de code sur la façon d'implémenter l'algorithme KMP en C#. En utilisant des tables de correspondance partielle, l'algorithme KMP peut améliorer efficacement l'efficacité de la correspondance de chaînes, en particulier lors du traitement de chaînes de texte volumineuses et de chaînes de modèles longues, avec de meilleures performances.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!