C "Stringsuche"

Hey, bin neu hier und bräuchte ein paar Ansatz Tipps. (Student, erstes Semester)

Die Folgende Aufgabe ist eine Übung die ich Abliefern muss. Leider habe ich vom Code her noch keine Idee wie ich das umsetzen soll.

Hier erstmal die Aufgabe, darunter schreibe ich mal wie ich das Lösen würde (ohne Code).

_____________________________________________________________
Schreiben Sie ein Programm mit einer Funktion folgender Signatur

char* suche (char *str, char *such, unsigned int n);

welche die Adresse des n-ten Vorkommens des Strings such in der Zeichenkette str ermittelt und den Zeiger auf den Beginn des n-ten Vorkommens der gesuchten Zeichenkette zurückliefert. Falls das n-te Vorkommen der gesuchten Zeichenkette nicht gefunden wurde, wird der NULL–Zeiger zurückgegeben.

Beispiele:
printf("%s", suche("dreierleieierei", "ei", 1) ); // ergibt: eierleieierei
printf("%s", suche("dreierleieierei", "ei", 3) ); // ergibt: eierei
printf("%s", suche("dreierleieierei", "ei", 4) ); // ergibt: ei
printf("%s", suche("barbara macht barbarei", "arba", 2) ); // ergibt: arbarei
if( suche("barbara macht barbarei ", "asdf", 1) == NULL )
printf("nicht vorhanden!"); // sollte ausgegeben werden, da es nicht vorkommt
if( suche("barbara macht barbarei ", "barba", 3) == NULL )
printf("nicht vorhanden!"); // sollte ausgegeben werden, da es nur 2-mal vorkommt

__________________________________________________________________

Also mein Gedankengang ist folgender:

Ich muss als erstes, die Strings vergleichen und dabei ne Variable mitlaufen lassen um zu sehen wie oft der "such"-String im "str"-String vorhanden ist.

Danach gehe ich in eine if ((Variable != NULL) && (Variable <= n)) dann "str"-string beim n-ten Zeichen abtrennen und "such" vor dem Rest String von "str".

Ausgabe/Rückgabe

ELSE
nicht vorhanden (falsch,NULL)



Ist das so vom Gedankengang korrekt, bzw. weit genug zerkleinert?
Vll kann mir jemand einen Tipp/Hilfe geben im Bezug auf die Strings(string.h verboten) wie ich das angehen kann in Code-Sprache.
________________________________


Vielen Dank schon mal

Ohne libraries würde ich das dann wohl so machen (Keine Lösung das musst du schon selber machen):

Du iterierst durch jeden Buchstaben des Übergabestrings und vergleichst ihn mit dem ersten Buchstaben des Matching Strings
Wenn das passt gehst du in beiden Strings einen weiter und vergleichst wieder die Buchstaben, das machst du solange bis der Matching String zuenden ist. Danach inkrementierst du eine Variable.
Die variable vergleichst du mit n und sobald es übereinstimmt gibst du einfach den Pointer aus der schleife zurück (da dieser dann auf die Stelle zeigt im String wo du mit Suchen warst)...

Der Rest ergibt sich von selbst...wenn der Übergabestring zuende ist bevor das n gematched wurde, gibt es keine Deckung und damit den NullPointer zurück

Weiß nicht ob das sonderlich verständlich war, aber letzendlich geht es in der Aufgabe nur darum Zeiger zu verstehen

knuth-morris-pratt

Ich würde so da drangehen, bin allerdings nicht mit den Standardmethoden von C vertraut.




Lg, Franz

PS: Aber strstr() ist wahrscheinlich in string.h?

PPS: Joah, hab nicht richtig gelesen - Dein Gedankengang war ja so ähnlich

Deine Gedankengaenge sind soweit richtig. Zum Stringmatching hat ein Vorposter ja schon Knuth-Morris-Pratt empfohlen. Mir fiele dazu noch Boyer-Moore ein.

Ansonsten:
1. Funktion Schreiben, die Index eines Substrings in einem String zurueckgibt
2. Index wegspeichern, Counter der Anzahl deiner Matches inkrementieren
3. Funktion StringMatch nochmals aufrufen, aber mit nem String an der Stelle d. vorherig gefundenen Index' abgeschnitten
4. Solange wiederholen, bis n Durchlaeufe erfolgreich waren oder der Suchstring leer ist
5. Sonderfaelle beachten (z.B. gesuchter String nicht enthalten, weniger als n Vorkommen; Genau auf die Arraygrenzen achten (seg. fault laesst gruessen))

just_for_fun schrieb:

Also mein Gedankengang ist folgender:

Ich muss als erstes, die Strings vergleichen und dabei ne Variable mitlaufen lassen um zu sehen wie oft der "such"-String im "str"-String vorhanden ist.

Danach gehe ich in eine if ((Variable != NULL) && (Variable <= n)) dann "str"-string beim n-ten Zeichen abtrennen und "such" vor dem Rest String von "str".

Ausgabe/Rückgabe

ELSE
nicht vorhanden (falsch,NULL)



Ist das so vom Gedankengang korrekt, bzw. weit genug zerkleinert?
Vll kann mir jemand einen Tipp/Hilfe geben im Bezug auf die Strings(string.h verboten) wie ich das angehen kann in Code-Sprache.
________________________________


Vielen Dank schon mal

Zum Vergrößern anklicken....

Deine Idee hat schon den richtigen Ansatz. Im zweiten Absatz wird es aber unnötig kompliziert. Wärend der Schleife in der du die Vorkommen des Substrings zählst kannst du schon testen, ob er n-mal enthalten ist und dann die Stelle des Vorkommens zurückgeben.
Wenn es an Ansätzen fehlt, mach dich erstmal an Teilprobleme:
- Iterieren über den String und jeden Character einzeln ausgeben
- Zählen bestimmter Character in einem String
- Die Stelle des n-ten 'A's eines Strings ausgeben
- Prüfen ob ein String ein Präfix eines anderen Strings ist (Substring der bei Index 0 anfängt)
Wenn du diese "Teil"probleme lösen kannst musst du sie nurnoch zum großen ganzen zusammensetzen.
Ich wünsche viel Erfolg!

Versuch bitte nicht, die hier vorgeschlagenen Knuth-Morris-Pratt oder Boyer-Moore matcher zu implementieren, das sind weiterführende, effiziente Algorithmen für das Problem. Ich weiß auch nicht warum man sowas hier vorschlägt, im ersten Programmierkurs geht es darum die Basis zu lernen und nicht "state-of-the-art" Algorithmen blind abzuschreiben oder nachzuvollziehen.

erstmal danke für die Tipps/Hilfe.

@NemesisFS

ich habe jetzt mal die anzahl des such-Strings im str-String abgezählt um zu wissen wie oft ich diesen habe.

________________________________________________________



Mein gedanke weiter wäre das ich den str-String an der n-ten stelle des such-Strings schneide und den Rest vom str-String in den such-String kopiere. Dann müsste ich ja die erste Ausgabe haben oder? Mein problem ist nur das ich das in Code umsetzen muss. (ohne fertige String-funktionen)

Das was du da hast funktioniert doch garnicht. Bisher suchst du nur hardcoded nach 'ei'. Du solltest dich mal mit der Bestimmung der Länge eines Strings bekannt machen. Tipp: Ein String in C ist nullterminiert, d.h. er endet immer mit '\0'.
"Abschneiden" musst du übrigens auch nichts, du brauchst nur den Pointer auf die gefundene Position zurückzugeben.
Im Grunde musst du es einfach so machen, wie von Master1991 in Post#2 beschrieben. Nur musst du bei der Rückgabe noch einmal um die Länge des Suchstrings zurückgehen.
Wichtig ist hier v.a. dass du dir klar machst, wie ein String aufgebaut ist und was dabei die Funktion eines Pointers auf einen char ist.

P.S. Dass bspw. immer genau einmal ausgeführt wird, also eine Schleife komplett unnötig, ist dir aber schon klar?

Man kann auch Buchstaben wie Zahlen verwenden, entweder als hash-wert oder als byte-folge. Du musst nur einmal iterieren um das Suchmuster zu identifizieren. Es ist kein extra Abgleich für den 2. oder n-ten Buchstaben im Suchmuster notwendig.
Es sollte vorher die Länge der zu durchsuchenden Kette ermittelt werden.
Wenn keine Standard-C-Funktion genutzt werden darf, dann in einer Endlosschleife mitzählen bis zum erreichen binären Null.

Beides simple Ansätze die der Aufgabe genügen sollten.

Recht elegant und mit weniger eigenem Code kann man die Aufgabe lösen, wenn die Funktion suche als Rekursive Funktion eingesetzt wird. Unter der Vorraussetzung, dass dieses Thema schon behandelt wurde. Sähe dann so aus:


Ist jetzt stark vereinfacht. Man muss dann bei jedem Aufruf str und such auf '/0' prüfen, auch NULL-Pointer Prüfung nicht vergessen, und n entsprechend dem Vorkommen von such bei einer weiteren Iteration vermindern. Ist dann n bei einem Aufruf 0 hat man den Pointer für den Teilstring gefunden und gibt den dann zurück. Wurde such nicht gefunden oder ist es nicht häufig genug vorhanden gibt es einen NULL-Pointer.

So eine Lösung mit Rekursiver Funktion hat den Vorteil, man muss nicht selbst mit etlichen zusätzlichen Variablen arbeiten und überlässt die Arbeit dem Compiler und Heap zur Laufzeit.

Wenn du schon Rekursion vorschlägst, dann schreib es doch wenigstens so, dass TCO greifen kann.

Inwieweit dürft ihr denn die C-Library benutzen?