Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

C++ - Najdłuższy wspólny podciąg

anasazi 04 Sie 2013 19:19 3138 11
  • #1 04 Sie 2013 19:19
    anasazi
    Poziom 8  

    Mam taką treść zadania:
    4. Proszę znaleźć najdłuŜsze jednakowe podciągi (podsłowa) słowa (ciągu znaków)
    składającego się z liter alfabetu łacińskiego A={a,b,c,...,x,y,z}. W pliku wejściowym znajduje
    się ciąg znaków do przeanalizowania. W pliku wyjściowym znajduje się znaleziony podciąg
    oraz liczby całkowite oznaczające jego połoŜenia w analizowanym tekście.
    Podsłowa składają się z sąsiadujących ze sobą liter. Podsłowa muszą być istotnie róŜne, to
    znaczy róŜnić się co najmniej jedną literą. Podsłowa mogą się nakrywać, to znaczy składać
    się z tych samych liter. W przypadku róŜnych podsłów o tej samej długości naleŜy podać ten,
    który zgodnie z porządkiem słownikowymi jest pierwszy.
    Przykład:
    Wprowadzone słowo: amalgamat
    Wynik:
    NajdłuŜszy podciąg: ama
    Pozycja: 1 6.,

    Napisaną część kodu:

    Kod: cpp
    Zaloguj się, aby zobaczyć kod



    Moje pytanie brzmi jak prawidłowo zrobić porównanie podciągu w danym ciągu oraz podanie pozycjonowania takich samych podciągów. Rzecz sie tyczy stringów, nie intów lub doubli.

    0 11
  • #2 04 Sie 2013 20:28
    stanleysts
    Poziom 27  

    Ja bym to zrobił tak:
    Wybieranie podciągów:
    bierzesz na początek pierwsze dwie litery i za pomocą funkcji jakichs wbudowanych (np string::find) szukasz sobie takich podciągów, jak takie są to taka wbudowana funkcja zwraca początek takiego znalezionego łańcucha.

    Potem bierzesz 3 litery 4 etc. do momentu aż nie znajdzie takiego podciągu. Jak już nie znalazł, to wiesz, że masz dalej nie szukać.

    Teraz znów zaczynasz od 2 liter, tylko, że to nie są już dwie pierwsze, ale 2ga i trzecia i powtarzasz dokładnie to co wcześniej.

    Mozesz sobie stowrzyć takie dwie zmiennne: obecnie najdłuższy podciąg i numery gdzie się znajduje.

    Jeśli napotkasz w kolejnych iteracjach na większy podciąg to to uaktualniasz.

    0
  • #4 05 Sie 2013 21:33
    stanleysts
    Poziom 27  

    Koledze chyba nie o to chodziło.

    0
  • #5 05 Sie 2013 22:19
    leoha
    Poziom 16  

    stanleysts napisał:
    Koledze chyba nie o to chodziło.

    Bardziej o szczególny przypadek tego

    0
  • #6 05 Sie 2013 22:32
    stanleysts
    Poziom 27  

    To już lepiej, nigdy nie byłem dobrym algorytmikiem, więc się nie wypowiadam na temat tego co tam jest, jesli to rozwiązanie nie musi byc optymalne, to moje uważam za proste w implementacji i skuteczne.

    0
  • #7 14 Sie 2013 19:53
    anasazi
    Poziom 8  

    W głównej mierze chodzi mi o najprostsze rozwiązanie, na tą chwile pal licho optymalizację.

    0
  • #8 15 Sie 2013 00:23
    the_fifth_horseman
    Poziom 32  

    Łap:

    Kod: C
    Zaloguj się, aby zobaczyć kod


    Tylko że ktokolwiek układał zadanie - mówiąc delikatnie - nie powinien uczyć.
    Treść zadania zawiera bardzo podstawowy bład logiczny - podsłowa nie mogą być naraz jednakowe i się różnić. "Podsłowa muszą (...) róŜnić się co najmniej jedną literą." oznacza coś całkowicie innego niż "podsłowa nie mogą zaczynać się w tej samej pozycji ciągu tekstowego" (na co wskazuje twój przykład).
    Drugi błąd znajduje się w przykładzie i świadczy, że osoba która układała zadanie nie sprawdziła własnego przykładu i nie ma pojęcia o tak podstawowym fakcie jak to iż adresowanie tablic w C i C++ zaczyna się nie od 1 ale od 0!
    3-znakowe podciągi z wyrazu"amalgamat" zaczynający się w indeksie 1 i 6 to "mal" i "mat"!

    0
  • #9 15 Sie 2013 09:46
    anasazi
    Poziom 8  

    Dzieki za wsparcie i uwagi, bardzo pomogliscie :)

    0
  • #10 15 Sie 2013 20:42
    anasazi
    Poziom 8  

    A ewentualnie jakies poprawki w moim kodzie zeby działał poprawnie ?

    0
  • #11 17 Sie 2013 16:21
    the_fifth_horseman
    Poziom 32  

    Nie ma w nim czego poprawiać - on nie jest błędny, tylko po prostu nie ma sensu.

    Nie przejmuj się: każdy od czegoś zaczynał. Jeżeli potrzebujesz objaśnienia jakiejś części rozwiązania, pytaj śmiało.

    0
  • #12 04 Paź 2013 20:12
    anasazi
    Poziom 8  

    Potrzebuje do poprawnego zaliczenia algorytmów ;/

    0