Stringverarbeitung mit Delphi

String-Funktionen selbst gemacht

Bisher haben wir nur vorhandene Delphi-Funktionen benutzt. Jetzt sehen wir uns auch mal an, wie diese funktionieren und wie man sowas selbst machen kann.

Dazu schreiben wir uns auch mal etwas, das man vielleicht sogar gebrauchen könnte… 😯

Pos sucht ja genau das erste Vorkommen eines Teilstrings im String. Als Variante davon wollen wir nun eine Funktion LastPos schreiben, die das letzte Vorkommen ermittelt.

Um die Benutzung möglichst ähnlich zu Pos zu machen, geben wir unserer Funktion die folgende Signatur:

LastPos

function LastPos(const SubStr, S: string): Integer;

SubStr: der String, nach dem gesucht werden soll
S: Der string, in dem gesucht werden soll
Rückgabewert: Die Position des letzten Vorkommens; ansonsten 0

Um so etwas zu realisieren brauchen wir zunächst mal eine Idee. Möglichkeiten gibts da mehere. Eine wäre solange mit PosEx zu suchen, bis PosEx nix mehr findet. Dann hat man das letzte Vorkommen. Das ist allerdings nicht sehr performant (funktioniert aber), da auch bei extrem langen Strings von vorne gesucht wird. Insbesondere bei sehr langen oder sehr vielen Strings (beispielsweise könnten Logfiles ausgewertet werden), fällt so etwas schon ins Gewicht.
Wir brauchen also eine neue, eine bessere Idee. Da wir das letzte Vorkommen suchen wollen, bietet es sich an, den String rückwärts zu durchsuchen. Und genau das machen wir auch. Wir gehen den String rückwärts durch und vergleichen ihn mit dem Substring. Dabei müssen wir nur darauf achten, dass wir den Substring auch von hinten durchgehen, da das letze Zeichen ja von hinten gesehen das erste ist.

Wenn die Idee nun klar ist, können wir uns nun auch der Implementierung widmen:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function LastPos(const SubStr, S: string): Integer;
var
  i: Integer;
  j: Integer;
begin
  Result := 0;    // noch nicht gefunden
  i := Length(S);
  j := Length(SubStr);

  while (i >= 1) and (j >= 1) do
  begin
    if S[i] = SubStr[j] then  // passt das Zeichen?
    begin
      // nächstes Zeichen untersuchen
      Dec(j);
    end
    else
    begin
      // wieder mit letztem SubStr-Zeichen anfangen
      i := i + Length(SubStr) - j;
      j := Length(SubStr);
    end;

    if j = 0 then
    begin
      Result := i;  // gefunden
    end;

    Dec(i); // nächstes Zeichen
  end;
end;

Wie funktioniert das Ganze jetzt? Das Prinzip ist eigentlich ganz einfach. Wir haben zwei Laufvariablen i und j. i läuft in S, j in SubStr und zwar jeweils von hinten nach vorne(wir wollen ja das letzte Vorkommen ermitteln). Wurde eine Übereinstimmung gefunden, wird j dekrementiert, d.h. wir testen dann auf Übereinstimmung mit dem zweitletzten Zeichen. Dann mit dem drittletzten, usw. Stimmt ein Zeichen nicht mit dem gesuchten überein, so wird wieder von vorne, d.h. von hinten angefangen, also wieder mit dem letzen Zeichen von SubStr. Irgendwann wird der Substring gefunden und i als Position zurückgegeben. Wird der Substring nicht gefunden bleibt Result 0.

Auch das ist nicht das schnellste Verfahren, für unsere Zwecke reicht es aber und es hat den Vorteil, dass es recht einfach zu verstehen ist und Verständlichkeit gehört zu den wichtigsten Eigenschaften von Quellcode.


Update (17.08.11): Bug in LastPos behoben

Kapitel: | Zurück | 1 | 2 | 3 | 4 |

3 Kommentare


  1. @Embarcadero (falls das jemand liest): Wär doch mal was, das direkt in die System.pas zu packen; könntet ihr auch gleich in eure elendslange Changelog-Datei schreiben und als neues Feature anpreisen 😉


  2. @Embarcadero (falls das jemand liest)

    Meinst du ehrlich?

    Wär doch mal was, das direkt in die System.pas zu packen

    Ein Tutorial in der System.pas? Ob das so sinnvoll ist… *kopfkratz*


  3. Hmm wollt das eigentlich zu der LastPos()-Funktion dazuschreiben, allerdings wird das dann zum gesamten Tutorial kommentiert.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert