Zitat von
marabu:
Wichtig ist, dass du den Algorithmus genau wiedergibst
marabu
das hab ich jetz beim erstellen des Beispiels auch gemerkt. Also hier der Algorithmus mit Komplexitet n * (n-k)
O(n^2) ist das dann wohl ?
Ich habe mich in meinem Einführungsbeispiel vertan. Der Algorithmus ist aber eigentlich richtig beschrieben.
Es ist im Prinzip eine Bestimmung irgendeines Maxwertes zweimal hintereinander.
für mmrtfff kommt immernoch mmrtfff raus.
Interessant wird es erst, wenn man hinter diese Sequenz zum Beispiel anfängt den Buchstaben a anzufügen.
also z.B. mmrtfffaa
da kommmt raus. mmfffffaa
Hier der Quelltext, der sagt vielleicht mehr als tausend Worte.
Delphi-Quellcode:
type
TDatenMaxCount = record
Buchstabe : Char;
Count : Integer;
StartIndex: Integer;
MaxLen : Integer;
end;
TDatenSieger = record
Buchstabe : Char;
MaxLen: Integer;
end;
//==============================================================================
function ermittle(Sequenz : String) : char;
var loop, charindex : Integer;
CountArray : array[0..255] of Integer;
Sieger : TDatenSieger;
MaxCount : TDatenMaxCount;
begin
for loop := 0 to high(CountArray) do
CountArray[loop] := 0;
MaxCount.Buchstabe := Sequenz[1];
Maxcount.Count := 1;
MaxCount.StartIndex := 1;
MaxCount.MaxLen := 1;
Sieger.Buchstabe := MaxCount.Buchstabe;
Sieger.MaxLen := 1;
for loop := 2 to length(Sequenz) do
begin
charindex := ord(Sequenz[loop]);
inc(CountArray[charindex]);
if charindex = ord(maxCount.Buchstabe)then
begin
inc(MaxCount.Count);
end else
begin
// Eventuell Neuen Count Max bestimmen
if CountArray[charindex] > MaxCount.Count then
begin
MaxCount.Count := CountArray[charindex];
MaxCount.StartIndex := loop;
MaxCount.Buchstabe := char(charIndex);
end;
end; // if else
// wird solange erhöht, bis der nächste Maxcount an dessen stelle kommt
MaxCount.MaxLen := loop - MaxCount.StartIndex;
// Längen Maximum .. Sieger bestimmen
// aktueller Maxcount kann den Sieger übertreffen
if MaxCount.MaxLen > Sieger.MaxLen then
begin
Sieger.Buchstabe := MaxCount.Buchstabe;
Sieger.MaxLen := MaxCount.MaxLen;
end;
end; // for
result := Sieger.Buchstabe;
end; // function ermittle
//==============================================================================
procedure TForm2.Button1Click(Sender: TObject);
var Eingabe, ausgabe, st : String;
i, len : Integer;
begin
Eingabe := 'mmrtfff';
ausgabe := '';
len := length(Eingabe);
for i := 0 to len -1 do
begin
st := copy(Eingabe, len -i, i+1);
ausgabe := Ermittle(st) + ausgabe;
end; // for
showmessage(ausgabe);
end; // buttonclick