Common blue - puzzle-uri online

Cea mai lungă secvență comună (NWP) - cea mai lungă șir de caractere care apar în aceeași ordine în două șiruri comparate. Elementele liantilor nu trebuie să fie unul lângă celălalt (acest lucru diferă de problema celei mai lungi substraturi comune). Rezolvarea acestei probleme este foarte utilă atunci când scrieți programe pentru a detecta modificările documentelor sau fișierelor sau când scrieți programe pentru identificarea plagiatelor.

Exemple:

Pentru abaabbaaa și babab, NWP-ul lor este baba și abab.

Pentru șirurile POLITECHNIKA și TOILET, NWP-ul lor este OLTA și OLEA.

Pentru șirurile 123 și 543, NWP-ul lor este 3. Este demn de remarcat faptul că implementarea soluției problemă se poate aplica atât unui șir înțeles ca un șir de litere, cuvinte sau chiar paragrafe.

Un algoritm care găsește o tabelă de lungime NWP din două șiruri

Idee

Problema NWP a două șiruri

        ȘI

    {\ displaystyle A}

   și

        B

    {\ displaystyle B}

   cu lungimi respectiv

        n

    {\ displaystyle n}

   și

        m

    {\ displaystyle m}

   poate fi rezolvată folosind metoda de programare dinamică.

Acest algoritm are complexitate de calcul a comenzii

        DESPRE

        (

        n

        *

        m

        )

        .

    {\ displaystyle O (n * m),}

   Unde

        n

    {\ displaystyle n}

   și

        m

    {\ displaystyle m}

   sunt lungimi de coarde

        ȘI

    {\ displaystyle A}

   și

        B

        .

    {\ displaystyle B.}

Acest algoritm creează un tablou bidimensional C (n per m) astfel încât valoarea lui C [i] [j] să fie lungimea NWP a subcărcilor

        ȘI

        [

        1..