Entwickler-Ecke
Algorithmen, Optimierung und Assembler - mehrere möglichkeiten wie ein substring belegt ist ?!
mwi - Mi 22.06.05 09:17
Titel: mehrere möglichkeiten wie ein substring belegt ist ?!
also mein problem ist folgendes:
ich möchte in einem string nach bestimmten komponenten/ausschnitten durchsuchen.
normaler weise macht man das ja folgender weise:
Delphi-Quelltext
1:
| integer:=pos(substring,string); |
und überprüft dann auf den integer wert.
nun ist es aber bei mir so, dass ich nach verschiedenen ausschnitten in einer zeile suchen möchte.
ich könnte zwar natürlich für jeden teilausschnitt eine neue substring abfrage erstellen, aber dass ist bei 8 verschiedenen nicht nur ne menge quelltext, sondern ein enormer bedarf an speicher.
darum wollte ich fragen, ob es da net eine elegantere lösung gibt?
Martin1966 - Mi 22.06.05 09:27
Titel: Re: mehrere möglichkeiten wie ein substring belegt ist ?!
hallo!
mwi hat folgendes geschrieben: |
aber dass ist bei 8 verschiedenen nicht nur ne menge quelltext |
lager es einfach in eine funktion aus und fertig.
mwi hat folgendes geschrieben: |
sondern ein enormer bedarf an speicher. |
warum sollte dabei übermäßig viel speicher belegt werden?
lg martin
alzaimar - Mi 22.06.05 09:33
Du suchst also nach eines Pos-Funktion, der Du einen Startindex mitgibst, ab der gesucht werden soll?
Suche nach faststrings.pas, eine Sammlung von schnellen Stringroutinen, oder hier im Forum nach bereits gelösten Problemem. Deine Frage ist sehr populär...
Ich habe mir so eine Funktion selbst geschrieben, allerdings sehr 'billig'. Für meinen Fall war die allerdings ausreichend schnell:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
| Function FastPos (Const aSubStr, aString : String; aStart : Integer) : Integer; Var c : Char; n,m : Integer; Begin Result := aStart; m := Length (aSubStr); n := Length (aString) - m + 1; c := aSubStr[1]; While Result < n do begin While aString [Result] <> c do If Result = n Then break else inc (Result); If Ansiuppercase (Copy (aString , Result, m)) = aSubStr then Exit; inc (Result); End; Result := 0 End; |
Parameter dürften klar sein. Funktionsweise: Ich suche einfach nach dem ersten Auftreten des ersten Zeichens vom SubString. Wenn ich den gefunden habe, schaue ich, ob der Rest auch passt.
Wenn Du einen richtig schnellen Algorithmus schreiben willst, suche nach KMP (Knuth-Morris-Pratt) oder nach Boyer-Moore.
Martin1966 - Mi 22.06.05 09:45
alzaimar hat folgendes geschrieben: |
Du suchst also nach eines Pos-Funktion, der Du einen Startindex mitgibst, ab der gesucht werden soll? |
wie kommst du darauf? Er hat doch geschrieben:
mwi hat folgendes geschrieben: |
nun ist es aber bei mir so, dass ich nach verschiedenen ausschnitten in einer zeile suchen möchte. |
ich hab das so verstanden, dass er in einer Zeile nach mehreren (verschiedenen) Strings suchen will.
lg martin
mwi - Mi 22.06.05 09:49
genau so siehts aus.
also wirklich nur die möglichkeir, den spaß auszulagern, damit der eigentliche code hübsch aussieht, ja???
das ding ist, dass mein programm auf grund seiner beschaffenheit/funktionalität sowieso net unbedingt wenig arbeitsspeicher schluckt, darum will ich eine möglichst kleine version haben.
alzaimar - Mi 22.06.05 11:39
Ach so, falsch verstanden. Egal. Dann solltest Du Dir einen endlichen Automaten bauen, um es schnell zu machen...
Oder eine Pos-Funktion, die ein Array Of SubString nimmt... Sollen die Positionen der gefundenen SubStrings auch jeweils geliefert werden?
Delphi-Quelltext
1:
| Function MultiPos (SubString : Array Of String; aString : String) : Array Of Integer; |
So etwa? Na, das ist doch einfach...
Allesquarks - Mi 22.06.05 15:30
Habe mir selbst mal eine Function zum durchsuchen von strings geschrieben weil ich pos nicht kannte.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| function findanykeywordascending(zeile:string;unten,oben:integer;var gefundeneswort:string;var erfolg:boolean):integer; var i,a,b,l:integer;dochnich:boolean;words:string;
begin erfolg:=false; for i:=unten to oben do begin b:=0; repeat b:=b+1;words:=knownkeywords[ord(zeile[i])-96,b];l:=length(words); dochnich:=false; For a:=1 to l-1 do begin if zeile[a+i]<>words[a+1] then begin dochnich:=true;end; end; if (dochnich=false) and (l<>0) then begin erfolg:=true;gefundeneswort:=words;findanykeywordascending:=i;exit;end; until (b>length(knownkeywords[ord(zeile[i])-96]));
end; end; |
knownkeyords ist ein zweidimensionales array, bei dem in einer spalte immer Wörter gleicher Anfangsbuchstaben stehen.
in der ersten Spalte also Anton, Arabien usw.
Meine function beendet sich sobald sie ein Wort gefunden hat, kannst ja aber in ner übergeordneten function die Suche ab da wieder aufnehmen.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!