Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

najdłuższy wspólny podciąg

Ostatnio zmodyfikowano 2015-05-09 18:06
Autor Wiadomość
kasiulla
Temat założony przez niniejszego użytkownika
najdłuższy wspólny podciąg
» 2015-05-08 17:08:21
Jestem bardzo początkującym programistą. Dostałam zadanie aby stworzyć algorytm znajdujący długość najdłuższego podciągu ciągu. Napisałam coś takiego:
C/C++
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int ilosc;
    string ciag;
    string podciag;
    int * ilosc_skladnikow;
   
    cout << "Ilosc podciagow: ";
    cin >> ilosc;
   
   
    cout << "Podaj ciag: ";
    cin >> ciag;
   
    ilosc_skladnikow = new int[ ilosc ];
   
    for( int n = 0; n < ilosc; n++ )
    {
        cout << " podciag z numerem  " <<( n + 1 ) << ": ";
        cin >> podciag;
        ilosc_skladnikow[ n ] = 0;
        int k = 0;
        for( int j = 0; j < podciag.length(); j++ ) {
            int l = 0;
            while( k + l < ciag.length() ) {
                if( podciag[ j ] == ciag[ k + l ] )
                {
                    ilosc_skladnikow[ n ] ++;
                    k += l + 1;
                }
                l++;
            }
        }
       
        cout << endl;
    }
    for( int n = 0; n < ilosc; n++ )
    {
        cout << "W popdciagu z numerem  " <<( n + 1 ) << "    zgadza sie  " << ilosc_skladnikow[ n ] << "  skladniki " << endl;
    }
   
    system( "pause" );
    return 0;
}
program działa, jednak na przykład dla ciągu ABGCD, najdłuższy wspólny podciąg ma długość 4 a pokazuje jedynie dwa (chodzi mi dokładnie o to, aby program pokazywał wszystkie wspólne litery w obu ciągach, nie ważnie w jakiej są kolejności). Proszę o pomoc w ewentualnej poprawie programu lub o pokazanie w czym jest problem :)
P-131888
michal11
» 2015-05-08 23:55:30
Przede wszystkim nie zwalniasz pamięci.
Robiłeś swój algorytm z tym http://pl.wikipedia.org/wiki​/Najd%C5%82u%C5%BCszy_wsp%C3%B3lny_podci%C4%85g ?
P-131922
kasiulla
Temat założony przez niniejszego użytkownika
» 2015-05-09 18:06:58
Nie próbowałam to zrobić bardziej tak na logikę. Problem jest z tym, że jak ten program znajdzie jakąś wspólną literkę podciągu z tym ciągiem podstawowym to ponownie przeszukuje go nie od początku tylko od tego miejsca gdzie była ta wspólna litera. A ja niestety nie umiem poprawic tego programu zeby działał jak nalezy:(
P-131943
« 1 »
  Strona 1 z 1