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!

user profile iconmwi hat folgendes geschrieben:
aber dass ist bei 8 verschiedenen nicht nur ne menge quelltext

lager es einfach in eine funktion aus und fertig.

user profile iconmwi 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

user profile iconalzaimar 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:
user profile iconmwi 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
                //hier müsste man noch absichern,dass words nicht leer ist
                if zeile[a+i]<>words[a+1then begin dochnich:=true;end;
             end;
         if (dochnich=false) and (l<>0then 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.