Common blue - online παζλ

Μεγαλύτερη κοινή ακολουθία (NWP) - η μεγαλύτερη συμβολοσειρά χαρακτήρων που εμφανίζονται με την ίδια σειρά σε δύο συγκριτικές συμβολοσειρές. Τα στοιχεία των συνδετικών δεν χρειάζεται να είναι το ένα δίπλα στο άλλο (αυτό διαφέρει από το πρόβλημα του μακρύτερου κοινού υποστρώματος). Η επίλυση αυτού του προβλήματος είναι πολύ χρήσιμη κατά τη σύνταξη προγραμμάτων για τον εντοπισμό αλλαγών σε έγγραφα ή αρχεία ή κατά τη σύνταξη προγραμμάτων για την αναγνώριση λογοκλοπών.

Παραδείγματα:

Για τα abaabbaaa και babab, το NWP τους είναι baba και abab.

Για τις χορδές POLITECHNIKA και TOILET, το NWP τους είναι OLTA και OLEA.

Για τις συμβολοσειρές 123 και 543 το NWP τους είναι 3. Αξίζει να σημειωθεί ότι η εφαρμογή της λύσης προβλήματος μπορεί να εφαρμοστεί τόσο σε μια συμβολοσειρά που νοείται ως μια σειρά γραμμάτων, λέξεων ή ακόμη και παραγράφων.

Ένας αλγόριθμος που βρίσκει έναν πίνακα μήκους NWP δύο χορδών

Ιδέα

Πρόβλημα NWP δύο χορδών

        ΚΑΙ

    {\ displaystyle A}

   και

        σι

    {\ displaystyle B}

   με μήκη αντίστοιχα

        ν

    {\ displaystyle n}

   και

        Μ

    {\ displaystyle m}

   μπορεί να λυθεί χρησιμοποιώντας τη μέθοδο δυναμικού προγραμματισμού.

Αυτός ο αλγόριθμος έχει υπολογιστική πολυπλοκότητα της παραγγελίας

        ΣΧΕΤΙΚΑ ΜΕ

        (

        ν

        *

        Μ

        )

        .

    {\ displaystyle O (n * m),}

   όπου

        ν

    {\ displaystyle n}

   και

        Μ

    {\ displaystyle m}

   είναι μήκη συμβολοσειράς

        ΚΑΙ

    {\ displaystyle A}

   και

        σι

        .

    {\ displaystyle B.}

Αυτός ο αλγόριθμος δημιουργεί μια δισδιάστατη συστοιχία C (n ανά m) έτσι ώστε η τιμή του C [i] [j] να είναι το μήκος του NWP των υποστρωμάτων

        ΚΑΙ

        [

        1.