Toon posts:

[C++] Hoe zoek ik de grootste gemeenschappelijke string

Pagina: 1

Acties:

49 views sinds 30-01-2008

maandag 18 november 2002 00:51

Acties:

Verwijderd

Topicstarter

OK, ik heb een probleem:
Ik moet vóór kwart voor 2 vandaag een programma in elkaar hebben zitten dat de 2 grootste gemeenschappelijke strings uitzoekt bij 2 strings, en ik heb al code die gemeenschappelijke strings van een bepaalde lengte uitzoekt, maar er werd uitdrukkelijk bij gezegd dat je het niet 'dom' met een forloopje mocht doen waarbij de lengte steeds 1 groter wordt.
Quote uit het blaadje:
"In dit deel van de opdr8 gaan we op zoek naar het langste patroon dat de twee strings gemeenschappelijk hebben. Je kunt dat primitief aanpakken door het programma van onderdeel 7.3 (zie hieronder) met steeds grotere waarden van de lengte van het te zoeken patroon op de ketens los te laten en met het opvoeren van de lengte zover door te gaan, dat voor een nog grotere lengte geen gemeenschappelijke delen meer bestaan.
Dat is echter een weinig sofisticated aanpak ... (denkend aan de complexiteit van de gehele operatie).

Meer voor de hand ligt het om te gaan werken met een 'flexibel-uitbreidbaar' zoekpatroon, waarbij we na het vinden van een match, het zoekpatroon met een téken en dus de patroonlengte met '1' proberen uit te breiden en daarmee verder te zoeken. Je gaat daar dan zo lang mee door, totdat een langer patroon geen gemeenschappelijke delen meer oplevert. Je zult dan het wel nog geldige langste patroon en de posities waarop dat patroon zowel in de eerste als in de tweede string optrad via aparte parameters moeten terugspelen naar de plaats van aanroep."

OK, ik snap dus zwaar weinig van dat geblaat, mijn code tot nu toe:

code:

#include <fstream>
#include <iostream>
#include <cstdlib>
#include <string>
#include <time.h>

using namespace std;

const int maxlengtearray = 61;  // lengtestring mag globaal zijn omdat het een constante is die makkelijk aangepast moet kunnen worden in de programmacode
time_t tijd;

void startTijdmeting ( time_t &start )
{
    time ( &start );
}

void geefVerstrekenTijdSinds ( time_t &start )
{
    time_t  finish;
    time ( &finish );

    const double verstreken_tijd = difftime ( finish, start );
    cout << "\nAantal seconden verstreken: " << verstreken_tijd << endl ;
}

void resetBool(bool teResettenBool[])
{   for (int teller = 0; teller <= maxlengtearray - 1; teller++)
        teResettenBool[teller] = false;
}

bool patroonKlopt(int beginPositie, char patroon[], char zoekString[], int lengtePatroon)
{   for (int teller = 0; teller <= lengtePatroon-1; teller++)
        if (zoekString[beginPositie+teller] != patroon[teller])
            return false;
    return true;
}

int komtVoorVanafPositie(int positie, char letter, char zoekstring[])
{   for(int teller = positie; teller <= strlen(zoekstring) - 1; teller++)
        if (letter == zoekstring[teller])
            return teller;
    return -1;
}

void printBoolArray(bool tePrinten[])
{   for(int teller = 0; teller <= maxlengtearray - 1; teller++)
    {   if (tePrinten[teller])
            cout << "^";
        else
            cout << " ";
    }
    cout << endl;
}

bool zoekPatroon(char patroon[], char zoekstring[], bool gevondenOpPlaats[])
{   resetBool(gevondenOpPlaats);    
    bool resultaat = false;
    int lengtepatroon = strlen(patroon);
    int positieNu = komtVoorVanafPositie(0, patroon[0], zoekstring);
    int lengtezoekstring = strlen(zoekstring);  
    while (positieNu >= 0 && positieNu <= (lengtezoekstring - lengtepatroon - 1))
    {   if (positieNu >= 0 && positieNu <= (lengtezoekstring - lengtepatroon - 1) && patroonKlopt(positieNu, patroon, zoekstring, lengtepatroon))
        {   gevondenOpPlaats[positieNu] = true;
            resultaat = true;
        }
        positieNu = komtVoorVanafPositie(positieNu+1, patroon[0], zoekstring);
    }
    return resultaat;
}

void lees(char regel[], ifstream& input_bestand)
{   input_bestand >> regel;
}

void zoekPatroonInPatroon(char string1[], char string2[], int lengte)
{   const int lengtestring1 = strlen(string1);
    const int lengtestring2 = strlen(string2);
    int stringletter;
    char stringdeel[maxlengtearray] = "";
    bool gevondenInRegel1[maxlengtearray];
    bool gevondenInRegel2[maxlengtearray];
    for (int teller = 0; teller <= lengtestring1-lengte; teller++)
    {   for (stringletter = 0; stringletter <= lengte-1; stringletter++)
            stringdeel[stringletter] = string1[teller+stringletter];
        //cout << endl << "!!" << stringdeel << "!!" << strlen(stringdeel) << endl;
        if (zoekPatroon(stringdeel, string1, gevondenInRegel1) && zoekPatroon(stringdeel, string2, gevondenInRegel2))
        {   cout << "Het patroon " << stringdeel << " is gevonden in allebei de strings:" << endl
                 << string1 << endl;
            printBoolArray(gevondenInRegel1);
            cout << string2 << endl;
            printBoolArray(gevondenInRegel2);
            cout << endl;
        }
    }
}

void main()
{   char regel1[maxlengtearray] = "";       // De eerste regel uit het bestand
    char regel2[maxlengtearray] = "";       // De tweede regel uit het bestand
    char patroon[maxlengtearray] = "";      // De door de gebruiker ingetypte string waarnaar gezocht moet worden
    int lengtepatroon;
    ifstream input_bestand;
    input_bestand.open("patroon.dat");
    lees(regel1, input_bestand);
    lees(regel2, input_bestand);
    cout << "Wat moet de lengte van de gemeenschappelijke string zijn? ";
    cin >> lengtepatroon;
    cout << endl;
    startTijdmeting(tijd);
    zoekPatroonInPatroon(regel1, regel2, lengtepatroon);
    geefVerstrekenTijdSinds(tijd);
}

Tis een beetje lang, dat weet ik, maar hopelijk neemt iemand de moeite om het te snappen want ik snap er dus echt geen kont van

Dikke $_/-\o_$ voor degene die mij helpt!

maandag 18 november 2002 01:02

Acties:

Verwijderd

Wat jij moet doen is op tijd aan je huiswerk beginnen, en tevens niet gelijk als een halve zool met zo'n teringlap code aan komen zetten. Dat gaat niemand voor je doorspitten.

Stop. Rewind. Play (op halve snelheid).

Probeer eerst eens je opdracht te begrijpen. Teken het mechanisme, zoals beschreven in je opdracht, uit. Als je snapt hoe het werkt, dan ga je pas met code kloten.

maandag 18 november 2002 01:05

Acties:

Verwijderd

Topicstarter

Probleem is dat ik dat stukje tekst uit de opdracht al niet snap (ook niet na het 10x doorgelezen te hebben), als iemand dat voor me kan vertalen is het al een hele grote schop vooruit, dan gaat het denk ik ook wel lukken...

maandag 18 november 2002 01:06

Acties:

Verwijderd

Lezen alleen is ook niet genoeg.

Teken het uit. Visualiseer het.

Je kan niet iets begrijpen als je het niet visualiseert.

maandag 18 november 2002 01:17

Acties:

Verwijderd

Hint:

String A = "aaa1bbcc"
String B = "zzzxxx1b"

Bekijk A[0]. Dat is een 'a'. Ga hiermee string B aflopen. Je vindt geen 'a', en dus is de langste overeenkomstige string in dit geval 0.

Herhaal deze stappen tot je komt bij A[3] == '1'. Ga met de '1' string B aflopen. Hee verrek... je vindt een '1' in B op B[6].

Nu is er een mogelijkheid dat niet alleen A[3] en B[6] overeenkomen, maar ook nog A[4] en B[7]. Een uitbreiding van je zoekpatroon bevestigt dat dit ook inderdaad zo is.

Dit is slechts een concreet gevalletje. Werk zelf de algemene techniek maar uit hoor.

maandag 18 november 2002 01:19

Acties:

Verwijderd

Topicstarter

bedankt $_/-\o_$

maandag 18 november 2002 01:27

Acties:

Verwijderd

You're welcome.

maandag 18 november 2002 01:38

Acties:

Verwijderd

Topicstarter

Alleen klopt er nu weer iets niet
string1 = "abcghijkqrstuvw"
string2 = "abcdefghijklmnopqrstuvwxyz" (alfabet dus)

programma gaat naar string1[0], komt ook in de ander voor, en t/m string1[2] klopt het nog. Daarna niet meer, dus het programma zegt "de grootste gemeenschappelijke string is abc", maar dat klopt niet, want het is qrstuvw. Hoe fix ik dit nou weer?

maandag 18 november 2002 01:49

Acties:

Frostie

Verwijderd schreef op 18 November 2002 @ 01:38:
Alleen klopt er nu weer iets niet
string1 = "abcghijkqrstuvw"
string2 = "abcdefghijklmnopqrstuvwxyz" (alfabet dus)

programma gaat naar string1[0], komt ook in de ander voor, en t/m string1[2] klopt het nog. Daarna niet meer, dus het programma zegt "de grootste gemeenschappelijke string is abc", maar dat klopt niet, want het is qrstuvw. Hoe fix ik dit nou weer?

Werk dan met 2 strings om op te slaan en 2 tellers voor de lengte. Als de lengte van de gevonden temp_string groter is dan de op dat moment langste string dan copy je de temp_string naar de long_string en temp_teller naar long_teller en ga je verder met checken van de te vergelijken strings. (Of je compared direct string lengte natuurlijk

)

pseudo code:

if strlen (temp_string) > long_string
temp_string = long_string

Oef dit was moeilijk

Toch vind ik het vreemd dat wij je hier met je huiswerk zitten te helpen (oja mijn oplossing is vast niet mooi maar hij werkt wel)

Weaseling out of things is important to learn. It's what separates us from the animals... except the weasel. Homer Simpson

maandag 18 november 2002 01:56

Acties:

nxt

Verwijderd schreef op 18 November 2002 @ 01:38:
Alleen klopt er nu weer iets niet
string1 = "abcghijkqrstuvw"
string2 = "abcdefghijklmnopqrstuvwxyz" (alfabet dus)

programma gaat naar string1[0], komt ook in de ander voor, en t/m string1[2] klopt het nog. Daarna niet meer, dus het programma zegt "de grootste gemeenschappelijke string is abc", maar dat klopt niet, want het is qrstuvw. Hoe fix ik dit nou weer?

dat komt waarschijnlijk omdat je niet verder kijkt zodra ie een oplossing gevonden heeft
probeer eens met recursie/backtracking o.i.d. alle mogelijkheden te verkrijgen
en daarna te kijken welke 't langste is

maandag 18 november 2002 02:26

Acties:

Verwijderd

Ik kom op zoiets uit:

C++:

#include <algorithm>
#include <utility>
 
template <typename It, typename It2>
std::pair<std::pair<It, It>, std::pair<It2, It2> > greatest_common_subrange (It b1, It e1, It2 b2, It e2)
{
  using std::pair;
  using std::make_pair;
 
  int longest (0);
  pair<pair<It, It>, pair<It2, It2> > r (make_pair(b1, b1), make_pair(b2, b2));
 
  for (; b1 != e1; ++b1)
    for (It2 tb2 = b2; (tb2 = std::find(tb2, e2, *b1)) != e2; ++tb2)
    {
      It te1 (b1 + min(e2 - tb2, e1 - b1));
      pair<It, It2> t = std::mismatch(b1, te1, tb2);
 
      int len (t.first - b1);
      if (len > longest)
      {
        longest = len;
        r.first = make_pair(b1, t.first);
        r.second = make_pair(tb2, t.second);
      }
    }
 
  return r;
}