Ein String im String suchen.

[canlot]

Hallo zusammen.
Als ich heute am proggen war, ist mir eine Idee gekommen.
Wie wäre es nochmal mit einem kleinen Algorithmus Wettkampf wie der von Wordcount?
Ich wäre für: siehe Überschrift.
Ich hab den Algorithmus fertig und würde gerne wissen wie andere den programmieren würden, und dementsprechend wie schnell sie sind
Wenn Xin Zeit und Lust hat die Sachen auszuwerten sowie andere mitzumachen wäre das echt cool
Was sagt ihr dazu?

[fat-lobyte]

Hallo zusammen.
Als ich heute am proggen war, ist mir eine Idee gekommen.
Wie wäre es nochmal mit einem kleinen Algorithmus Wettkampf wie der von Wordcount?
Ich wäre für: siehe Überschrift.
Ich hab den Algorithmus fertig und würde gerne wissen wie andere den programmieren würden, und dementsprechend wie schnell sie sind
Wenn Xin Zeit und Lust hat die Sachen auszuwerten sowie andere mitzumachen wäre das echt cool
Was sagt ihr dazu?

Wie sind denn die Strings gegeben? Ist der Anfang und das Ende gegeben? Oder nur der Anfang und die länge? Oder nur der Anfang, das Ende ist mit '\0' begrenzt?
Was soll passieren wenn ein String länger als der ander ist?
Was soll passieren wenn der String nicht gefunden wurde?
Wie soll man mit mehreren Treffern umgehen?
Was soll überhaupt zurückgegeben werden?

Bitte etwas präzisieren

[canlot]

Wie sind denn die Strings gegeben? Ist der Anfang und das Ende gegeben? Oder nur der Anfang und die länge? Oder nur der Anfang, das Ende ist mit '\0' begrenzt?

Der Anfang ist gegeben und das Ende ist halt mit '\0' gekennzeichnet.

Was soll passieren wenn ein String länger als der ander ist?

Habe ich nicht berücksichtigt.

Was soll passieren wenn der String nicht gefunden wurde?

return 1;

Wie soll man mit mehreren Treffern umgehen?

Habe ich ebenfalls nicht berücksichtigt.

Was soll überhaupt zurückgegeben werden?

return 0 für gefundenen String und return 1 für nicht gefundenen String.
Bei mir sucht er den Text nach den String ab und wen er ihn gefunden hat den beendet er sich mit return 0.
Was meint ihr dazu?

[Xin]

Grundsätzlich kann man das gerne machen.

Aber bei der Suche gibt es viele Fragen. Ist zum Beispiel wichtig, wo er gefunden wurde? Wie oft? Und wenn wie oft, wird soll dann "greedy" gesucht werden?
Greedy bedeutet, dass der String "ana" in "Banana" zweimal vorkommt, nämlich "bANAna" und "banANA". Dabei wird ein 'A' für zwei Ergebnisse genutzt. Man kann natürlich auch den gefundenen String nicht weiter prüfen, dann findet man nur "bANAna" und das wars.

Wie lang soll der gesuchte, bzw. der zu durchsuchende String sein? Bei einem kurzem zu durchsuchendem String, lohnt keine Untersuchung des Suchmusters.
Wieviele Strings werden in dem Text gesucht? Bei nur einem String, lohnt sich keine Untersuchung des zu durchsuchenden Strings?

Ich finde das Thema interessant, denn je nach Aufgabenstellung muss ich mich eh mit dem Thema noch für die Suchmaschine beschäftigen, die ja genau das zum Thema hat. ^^

[cloidnerux]

Mich Interessiert es auch.
Ich würde selber folgende Parameter nehmen:
Es soll zurückgegeben werden wie viele Vorkommen es gibt, wird der zu suchende Text nicht gefunden soll 0 zurückgegeben werden.
Es wird nicht greedy gesucht.
Der zu Durchsuchende text wird wieder groß, wie beim WordCount test, damit man gute Zeitwerte hat.
Gesucht wird nach einem Wort bzw einem Fragment.
Das Ende ist mit \0 gekennzeichnet, das gibt jedem die Möglichkeit den String selber irgendwie zu bemessen.

Das würde für mich folgende Funktionsdeklaration geben:

int SearchForString(char* base, char* target)

[Xin]

int SearchForString(char* base, char* target)

Ich möchte eine Festlegung wieviele unterschiedliche Worte im gleichen Text gesucht werden sollen, bzw. wieviele gleiche Worte in unterschiedlichen Texten gesucht werden sollen.

Und ich möchte eine Information, ob der zu durchsuchenden Texte kurz (bis 1KB) oder lang (>1 GB) groß ist. Also grundsätzlich jetzt im Testaufbau, damit jeder von gleichen Konditionen ausgehen kann.

Falls verfügbar, hätte ich die Längen-Information auch gerne als Parameter. Das kann man natürlich auch ablehnen, was dann bedeutet, dass das Nullbyte selbst erkannt werden muss, was allerdings die Optimierungsmöglichkeiten stark einschränkt.

Code: Alles auswählen

unsigned int SearchForString(char* base, unsigned int baseLength, char* target, unsigned int targetLength)

[canlot]

Ist greedy jetzt wenn man im gleichen wort 2 mal suchen darf?
Ich bin für den Nullbyte und die Textgröße soll auch möglichst groß sein.

[Xin]

Ist greedy jetzt wenn man im gleichen wort 2 mal suchen darf?

Wie beschrieben: Das nächste gefundene Wort darf im bereits gefundenen Wort beginnen.

Ein nicht gieriger Algorithmus würde das gefundene Wort überspringen und dahinter weitersuchen.

[Xin]

Ich push das hier nochmal... das Wetter ist immernoch zu gut, als das viele Leute aktiv würden, wie mir scheint.

canlot: Du legst die Bedingungen fest, dann kann's losgehen!

[nufan]

canlot: Du legst die Bedingungen fest, dann kann's losgehen!

Push ^^