Ο αλγόριθμος Knuth-Morris-Pratt (KMP) είναι ένας αλγόριθμος αναζήτησης προτύπων σε κείμενα. Ο βασικός στόχος του είναι να εντοπίσει όλες τις εμφανίσεις ενός προκαθορισμένου μοτίβου σε ένα κείμενο, αποφεύγοντας περιττές συγκρίσεις.

Βήματα του αλγορίθμου Knuth-Morris-Pratt (KMP):

Δημιουργία του πίνακα προθεμάτων (πίνακα LPS – Longest Prefix Suffix):
- Αυτός ο πίνακας χρησιμοποιείται για να αποφεύγονται περιττές συγκρίσεις στο κείμενο. Υπολογίζεται με βάση το πρότυπο (μοτίβο) και προσδιορίζει το πιο μεγάλο πρόθεμα του προτύπου που είναι και προθέματος και επίθημα σε κάθε θέση.
Αναζήτηση με χρήση του πίνακα LPS:
- Ξεκινώντας από την αρχή του κειμένου, συγκρίνουμε το μοτίβο με το κείμενο χρησιμοποιώντας τον πίνακα προθεμάτων.
- Όταν βρίσκουμε μία μη αντιστοίχιση σε έναν χαρακτήρα του κειμένου, το μοτίβο μετακινείται δεξιά κατά το μέγεθος του πίνακα LPS για να συνεχίσει την αναζήτηση.

Πλεονεκτήματα του KMP:

Αποτελεσματικότητα: Ο KMP είναι αποτελεσματικός αλγόριθμος, ιδιαίτερα όταν το μοτίβο είναι μεγάλο ή όταν το κείμενο είναι μεγάλο.
Χρονική πολυπλοκότητα: Η χρονική πολυπλοκότητα του KMP είναι O(m + n), όπου m είναι το μήκος του μοτίβου και n είναι το μήκος του κειμένου. Αυτό το καθιστά αποδοτικό για μεγάλα σύνολα δεδομένων.

Εφαρμογές του KMP:

Ο KMP χρησιμοποιείται ευρέως σε εφαρμογές που απαιτούν αναζήτηση συμβολοσειρών, όπως:

Αναζήτηση σε κείμενα ή αρχεία για συγκεκριμένα μοτίβα.
Αναζήτηση σε βάσεις δεδομένων για καταχωρήσεις που πληρούν συγκεκριμένα κριτήρια.

Ο KMP αναγνωρίζεται για την αποτελεσματικότητα και την ευρεία χρήση του σε εφαρμογές που απαιτούν γρήγορη και ακριβή αναζήτηση προτύπων σε κείμενα.

Ψευδογλώσσα:

Ο πίνακας πίνακας_προτύπου υπολογίζεται από το πρότυπο για να βοηθήσει στην αποφυγή περιττών συγκρίσεων κατά την αναζήτηση.
Ο αλγόριθμος χρησιμοποιεί δύο δείκτες, i για το κείμενο και j για το πρότυπο, για να εκτελέσει την αναζήτηση.
Όταν ένα τμήμα του κειμένου ταιριάζει με το πρότυπο, ελέγχει αν έχει βρει μια αντιστοιχία πλήρους πρότυπου και τυπώνει τη θέση της εύρεσης.

Διαδικασία KMP(κείμενο, πρότυπο)
    Αρχή
        δημιουργία πίνακα πίνακας_προτύπου μήκος(πρότυπο)
        πίνακας_προτύπου[0] ← 0
        μήκος_προτύπου ← μήκος(πρότυπο)
        προηγούμενο_μήκος ← 0

        i ← 1
        ενώ i < μήκος(πρότυπο) επανάλαβε
            αν πρότυπο[i] = πρότυπο[προηγούμενο_μήκος] τότε
                προηγούμενο_μήκος ← προηγούμενο_μήκος + 1
                πίνακας_προτύπου[i] ← προηγούμενο_μήκος
                i ← i + 1
            αλλιώς
                αν προηγούμενο_μήκος ≠ 0 τότε
                    προηγούμενο_μήκος ← πίνακας_προτύπου[προηγούμενο_μήκος - 1]
                αλλιώς
                    πίνακας_προτύπου[i] ← 0
                    i ← i + 1
                τέλος_αν
            τέλος_αν
        τέλος_επανάληψη

        i ← 0
        j ← 0
        ενώ i < μήκος(κείμενο) επανάλαβε
            αν πρότυπο[j] = κείμενο[i] τότε
                j ← j + 1
                i ← i + 1
            τέλος_αν

            αν j = μήκος(πρότυπο) τότε
                Εκτύπωσε("Βρέθηκε πρότυπο στη θέση " + (i - j))
                j ← πίνακας_προτύπου[j - 1]
            αλλιώς αν i < μήκος(κείμενο) και πρότυπο[j] ≠ κείμενο[i] τότε
                αν j ≠ 0 τότε
                    j ← πίνακας_προτύπου[j - 1]
                αλλιώς
                    i ← i + 1
                τέλος_αν
            τέλος_αν
        τέλος_επανάληψη
    Τέλος

Knuth-Morris-Pratt-KMP Download

C#:

Η μέθοδος ComputeLPSArray υπολογίζει τον πίνακα lps (Longest Prefix Suffix) για το πρότυπο.
Η μέθοδος KMPSearch χρησιμοποιεί αυτόν τον πίνακα για να εκτελέσει την αναζήτηση στο κείμενο. Η μέθοδος ComputeLPSArray αρχικοποιεί τον πίνακα lps με βάση το πρότυπο, υπολογίζοντας τις τιμές των μακριώντων προθέσεων επιθέτων για κάθε θέση του προτύπου. Η μέθοδος KMPSearch συγκρίνει το πρότυπο με το κείμενο, χρησιμοποιώντας τον πίνακα lps για να καθορίσει την επόμενη θέση στο κείμενο που θα ξεκινήσει την επόμενη σύγκριση, αν το πρότυπο δεν ταιριάξει με το κείμενο στην τρέχουσα θέση. Η συνδυαστική χρήση αυτών των μεθόδων καθιστά τον αλγόριθμο KMP αποδοτικό και κατάλληλο για εφαρμογές που απαιτούν γρήγορη αναζήτηση υποσυμβολοσειρών σε μεγάλα κείμενα, ενώ η πολυπλοκότητα του παραμένει σε γραμμικό επίπεδο σε σχέση με το συνολικό μήκος του κειμένου και του προτύπου.

using System;

class KMPAlgorithm
{
    public static int[] ComputeLPSArray(string pattern)
    {
        int m = pattern.Length;
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < m)
        {
            if (pattern[i] == pattern[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {
                if (len != 0)
                {
                    len = lps[len - 1];
                }
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    public static void KMPSearch(string text, string pattern)
    {
        int n = text.Length;
        int m = pattern.Length;

        int[] lps = ComputeLPSArray(pattern);
        int i = 0;  // index for text[]
        int j = 0;  // index for pattern[]

        while (i < n)
        {
            if (pattern[j] == text[i])
            {
                j++;
                i++;
            }

            if (j == m)
            {
                Console.WriteLine("Pattern found at index " + (i - j));
                j = lps[j - 1];
            }
            else if (i < n && pattern[j] != text[i])
            {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }
    }

    public static void Main()
    {
        string text = "ABABDABACDABABCABAB";
        string pattern = "ABABCABAB";

        Console.WriteLine("Text: " + text);
        Console.WriteLine("Pattern: " + pattern);
        Console.WriteLine("Pattern found at indices:");
        KMPSearch(text, pattern);
    }
}