Informatyka strings

1

Znajdowanie najdłuższego powtarzającego się podsekwencji

Biorąc pod uwagę ciąg sss, Chciałbym znaleźć najdłuższą powtarzającą się (przynajmniej dwukrotnie) podsekwencję. To znaczy, chciałbym znaleźć ciągwww który jest podciągiem (nie musi być ciągły) z sss takie, że w=w′⋅w′w=w′⋅w′w=w' \cdot w' . To jest,wwwto ciąg, którego połówki pojawiają się dwa razy z rzędu. Zauważ, żewww jest podsekwencją sss, ale …

9 algorithms optimization dynamic-programming strings subsequences

1

Biorąc pod uwagę n ciągów, czy jeden z nich jest podciągiem innego?

Załóżmy, że otrzymaliśmy zbiór ciągów, . Chciałbym wiedzieć, czy którykolwiek z tych ciągów jest podciągiem dowolnego innego ciągu w kolekcji. Innymi słowy, chciałbym algorytm dla następującego zadania:nnnS.1, ... ,S.nS1,…,SnS_1,\dots,S_n Dane wejściowe:S.1, ... ,S.nS1,…,SnS_1,\dots,S_n Wyjście: takie, że jest podłańcuchem i , lub None, jeśli nie takie existja , ji,ji,jS.jaSiS_iS.jotSjS_ji ≠ ji≠ji\ne …

9 algorithms strings efficiency substrings

1

Znajdź najdłuższy powtarzający się wzór w ciągu

Szukam wydajnego algorytmu do znajdowania najdłuższego powtarzającego się wzorca w ciągu. Weźmy na przykład następujący ciąg liczb: 5431428571428571428571428571427623874534. Jak widać, 142857142857jest to najdłuższy wzór, który powtarza się kilka razy (przynajmniej dwa razy) w tym ciągu. Powtarzany ciąg nie powinien zawierać żadnych pomysłów, a nie brutalną siłę?

9 algorithms strings subsequences

Pytania otagowane jako strings