Rekusiv Reichenkette suchen

SvenJungwird

Hallo,

leider habe ich meine Funktionsdatei gelöscht. Deshab muss ich die Funktion neu implementieren. Ich weiß aber nicht mehr genau wie ich diese Programmiert habe. Ein paar Grund züge..

Diese Funktion soll durch Rekursion

int zeichenkette_suchen_rekursiv(string text, string zkette, unsigned int, text_pos = 0, unsigned int text_such_pos = 0, unsigned int zkette_such_pos = 0
);

ermitteln, ob die Zeichenkette zkette in dem
einzeiligen Text text vorkommt. Wobei ich dies ohne Schleifen realisieren möchte, deshalb Reskusion.

Ablauf:
text_pos bezeichnet die Position innerhalb von text, ab der gerade
versucht wird, die Zeichenkette zkette zu finden. Wenn an einer
text_pos das linkeste Zeichen der gesuchten Zeichenkette gefunden wird,
so werden ab dieser Stelle mittels der Positionszähler text_such_pos
(aktuelle Vergleichsposition im einzeiligen Text) und zkette_such_pos
(aktuelle Vergleichsposition in der zu suchenden Zeichenkette) auch alle
weiteren Zeichen des Textes und der Such-Zeichenkette rekursiv
verglichen.
Sollte die Zeichenkette nicht in dem Text vorkommen, so soll der Wert -1
zurückgegeben werden. Anderenfalls wir die Startposition zurückgegeben,
ab der das erste (linkeste) Vorkommen von zkette in text beginnt. Die
Zählung der Positionen im Text beginnt bei 0.

Beispiel:
zeichenkette_finden_rekursiv("abcabcdef", "abcd", 0, 0, 0)
Vergleiche a und a: gleich
zeichenkette_finden_rekursiv("abcabcdef", "abcd", 0, 1, 1)
Vergleiche b und b: gleich
zeichenkette_finden_rekursiv("abcabcdef", "abcd", 0, 2, 2)
Vergleiche c und c: gleich
zeichenkette_finden_rekursiv("abcabcdef", "abcd", 0, 3, 3)
Vergleiche a und d: nicht gleich
zeichenkette_finden_rekursiv("abcabcdef", "abcd", 1, 1, 0)
Vergleiche b und a: nicht gleich

Ausgabe (Console)
Bitte geben Sie den Text ein: abcdefg
Bitte geben Sie die zu suchende Zeichenkette ein: bcd99
Die Zeichenkette 'bcd99' ist NICHT in dem Text 'abcdefg' enthalten.
Eventuell kann mir jemand bei der Implementierung helfen, ich wäre sehr dankbar!

1. Verwende Versionskontrollsoftware, dann kannst du nach dem Löschen die Datei einfach wiederherstellen.
2. Warum möchtest du das rekursiv und ohne Schleifen machen? Da gibt es keinen guten Grund für. Zumal die Strings auch noch per Value übergeben werden. Viel Spaß bei längeren Strings - der nächste Stack Overflow wartet schon. Sicherlich wäre zur Lösung ein Algorithmus wie Boyer-Moore besser geeignet!
3. Ja, wir könnten dir helfen. Aber was hast du schon selbst versucht und wo ist das Problem? Schildere das genaue Problem, an dem du nicht weiterkommst und zeig relevanten Code, an dem du nicht weiterkommst!

SvenJungwird

1. Pc formatiert.
2. Weil ich gerne rekursion üben möchte. Gerade anhand von Beispielen lerne ich.

3. Das Problem ist, ich weiß nicht wie ich das beschriebene in code umsetze. Ich habe damals ziemlich lange gebraucht, wäre aber dankbar wenn jemand mir dabei hilft und diese resusionsfunktion programmiert.

Danke.

MFK

Du kannst den Parameter text_such_pos weglassen, den brauchst du nicht.

SvenJungwird, ernsthaft, das willst du nicht machen, nicht haben, nicht lesen.

Such dir ein sinnvolleres Beispiel aus, wenn du Rekursion üben willst.

DaTaCrAsH

Aktuelle Aufgabe bei uns in Grundlagen der Programmierung auf der FH Aachen.

Wie ist dein Ansatz?

Swordfish

bool find_str_rec( char const * haystack, char const * needle )
{
	if( *haystack == *needle ) {
		if( *needle ) {
			return find_str_rec( haystack + 1, needle + 1 );
		} else { //   *needle == '\0'   &&   *haystack == '\0'
			return true;
		}
	} else if( *haystack == '\0' ) return false;

	return find_str_rec( haystack + 1, needle );
}

aber dabei hab ich sicher was übersehen.

Komischer Algorithmus

Du hast was übersehen:

find_str_rec("axb", "ab")

Außerdem: nimm an, du suchst den String "a" in "abbbbbbbbbbbbbbb". Dann findest du ihn sofort, dein Algo geht dann aber noch ganz bis zum Ende des Haystacks durch.

Also insgesamt: so gehts nicht!

Swordfish

wob schrieb:

Du hast was übersehen:

*schulterzuck* sag ich doch?

EOP

find_str_rec( char const * haystack, char const * needle )
{
    if( *haystack == *needle )

Das ist also C++? Fast so fürchterlich wie mein eigener Code.