• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zrobienie algorytmu, która wyznacza wspólny subkod

VPS Starter Arubacloud
0 głosów
77 wizyt
pytanie zadane 17 listopada 2020 w Algorytmy przez SmaczySchabowy Początkujący (270 p.)

Celem programu jest wyznaczenie najdłuższego z możliwych subkodu genetycznego dla dwóch różnych kodów. Subkod genetyczny wyznaczony dla dwóch odmian stanowi uporządkowany (najdłuższy z możliwych) ciąg znaków, które w niezmienionej kolejności występują zarówno w charakterystyce jednej jak i drugiej odmiany. Przykład:

In:

45A64D5F5B342

456345AC6AB7345

Out:

45645B34

Osobiście próbowałem to zrobić tak, że iterowałem po tych kodach niczym po tablicy dwuwymiarowej po kolei dla każdego chara z pierwszego kodu iterowałem po wszystkich z drugiego z takim samym indeksem lub większym i porównywałem. Jeśli znaki pod tymi indeksami z obu kodów się zgadzały to dodawałem ten znak do listy która przechowywała subkod. Niestety w tym algorytmie jest problem z wyznaczeniem najdłuższego możliwego subkodu, gdyż dla pierwszego kodu genetycznego wszystko idzie po kolei a czasami trzeba któryś znak ominąć aby powstał najdłuższy możliwy subkod tak jak tutaj niżej, kod mógł się zaczynać równie dobrze '45A' a zaczyna się '456' zatem 'A' zostało ominięte, ponieważ dla tego przypadku subkod nie będzie najdłuższy. Czy ma ktoś pomysł jak napisać taki algorytm który dla dwóch kodów genetycznych będzie wyznaczać najdłuższy subkod? Z góry dziękuję za pomoc i mam nadzieje że dobrze nakreśliłem ten problem.

1 odpowiedź

+1 głos
odpowiedź 17 listopada 2020 przez Whistleroosh Maniak (56,980 p.)
wybrane 5 stycznia 2021 przez SmaczySchabowy
 
Najlepsza
To jest popularny problem algorytmiczny, który można rozwiązać w O(n^2). Poczytaj o najdłuższym wspólnym podciągu i algorytmach, które go wyznaczają

Podobne pytania

0 głosów
1 odpowiedź 144 wizyt
0 głosów
0 odpowiedzi 307 wizyt
pytanie zadane 3 sierpnia 2023 w Algorytmy przez Mariusz M Obywatel (1,670 p.)

92,843 zapytań

141,782 odpowiedzi

320,858 komentarzy

62,174 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...