C# Learning

Τι είναι ο Αλγόριθμος Rabin-Karp;

Φαντάσου ότι έχεις ένα μεγάλο βιβλίο και ψάχνεις για μια συγκεκριμένη λέξη. Εάν η λέξη είναι πολύ κοινή, μπορεί να είναι δύσκολο να τη βρεις, ειδικά αν είναι πολλές φορές στο βιβλίο.

Ο αλγόριθμος Rabin-Karp είναι ένας έξυπνος τρόπος να βρεις μια λέξη (ή “μοτίβο”) μέσα σε ένα μεγάλο κείμενο χρησιμοποιώντας μια τεχνική που ονομάζεται “χαρτογράφηση” (hashing). Στην ουσία, το κάνει γρήγορα και με έξυπνο τρόπο!

Πώς Λειτουργεί;

1. Δημιουργία Χαρτών:
   • Φτιάχνεις ένα “χάρτη” για τη λέξη που ψάχνεις (το μοτίβο) και ένα χάρτη για το κείμενο που ελέγχεις.
2. Σύγκριση Χαρτών:
   • Συγκρίνεις τους χάρτες αντί να συγκρίνεις τη λέξη κατευθείαν. Αυτό είναι πολύ πιο γρήγορο!
3. Μετακίνηση:
   • Μετακινείς τον “χάρτη” σας σε νέα θέσεις στο κείμενο και συγκρίνεις ξανά.
4. Εύρεση:
   • Εάν οι χάρτες ταιριάζουν, τότε έχεις βρει τη λέξη στο κείμενο!

Παράδειγμα σε C#

Ας δούμε πώς να εφαρμόσουμε τον αλγόριθμο Rabin-Karp στην C# για να βρούμε ένα μοτίβο σε ένα κείμενο.

1. Δημιουργία του Προγράμματος:

using System;

class Program
{
    // Μέθοδος για να υπολογίσουμε την τιμή hash ενός κειμένου
    static long CalculateHash(string str, int prime, int modulus)
    {
        long hash = 0;
        foreach (char c in str)
        {
            hash = (hash * prime + c) % modulus;
        }
        return hash;
    }

    // Μέθοδος για να βρούμε το μοτίβο στο κείμενο χρησιμοποιώντας τον αλγόριθμο Rabin-Karp
    static void RabinKarpSearch(string text, string pattern)
    {
        int m = pattern.Length;
        int n = text.Length;
        int prime = 101; // Πρώτος αριθμός για το hash
        int modulus = 1000000007; // Μεγάλος αριθμός για το hash

        long patternHash = CalculateHash(pattern, prime, modulus);
        long textHash = CalculateHash(text.Substring(0, m), prime, modulus);

        // Συγκρίνουμε την αρχική τιμή hash
        if (textHash == patternHash && text.Substring(0, m) == pattern)
        {
            Console.WriteLine("Βρέθηκε το μοτίβο στην θέση 0.");
        }

        // Μετακινούμε το "παράθυρο" και συγκρίνουμε ξανά
        for (int i = 1; i <= n - m; i++)
        {
            // Υπολογίζουμε το hash για την επόμενη θέση
            textHash = (textHash - text[i - 1] * (long)Math.Pow(prime, m - 1)) * prime + text[i + m - 1];
            textHash = (textHash + modulus) % modulus;

            // Συγκρίνουμε το hash και το πραγματικό κείμενο
            if (textHash == patternHash && text.Substring(i, m) == pattern)
            {
                Console.WriteLine("Βρέθηκε το μοτίβο στην θέση " + i + ".");
            }
        }
    }

    static void Main(string[] args)
    {
        string text = "Αυτή είναι μια δοκιμή για τον αλγόριθμο Rabin-Karp.";
        string pattern = "Rabin";

        RabinKarpSearch(text, pattern);
    }
}

Τι Κάνουμε Εδώ:

1. Υπολογισμός Hash:
   • Χρησιμοποιούμε τη μέθοδο CalculateHash για να υπολογίσουμε τη “χρηματική τιμή” (hash) της λέξης και του κειμένου.
2. Αναζήτηση με Rabin-Karp:
   • Δημιουργούμε hash για το μοτίβο και το αρχικό κομμάτι του κειμένου.
   • Συγκρίνουμε το hash του μοτίβου με το hash του κειμένου. Εάν ταιριάζουν, ελέγχουμε αν η λέξη ταιριάζει πραγματικά.
   • Μετακινούμε το “παράθυρο” και επαναλαμβάνουμε τη διαδικασία.
3. Εμφάνιση Αποτελέσματος:
   • Εμφανίζουμε τις θέσεις όπου βρήκαμε το μοτίβο στο κείμενο.

Συνοπτικά

• Rabin-Karp: Είναι μια μέθοδος για να βρεις ένα μοτίβο μέσα σε ένα κείμενο γρήγορα χρησιμοποιώντας “χάρτες” (hashes).
• C#: Χρησιμοποιούμε κώδικα C# για να εφαρμόσουμε αυτή τη μέθοδο και να βρούμε το μοτίβο.