najdłuższy wspólny podciąg
Ostatnio zmodyfikowano 2015-05-09 18:06
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: #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 :) |
|
michal11 |
» 2015-05-08 23:55:30 |
|
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:( |
|
« 1 » |