program SegmentTextPascal;
{$mode objfpc}{$H+}
uses
SysUtils;
type
TStringArray = array of string;
{
Helper: check if a substring is in the dictionary.
}
function dict_contains(const candidate: string; const dict: array of string): Boolean;
var
i: SizeInt;
begin
Result := False;
for i := 0 to High(dict) do
if candidate = dict[i] then
Exit(True);
end;
{
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
}
function segment_text(const text: string; const dict: array of string): TStringArray;
var
n: SizeInt;
dp: array of SizeInt;
valid: array of Boolean;
i, j: SizeInt;
len: SizeInt;
candidate: string;
words: TStringArray;
count: SizeInt;
w: string;
tmp: string;
begin
SetLength(Result, 0); { <-- FIX: initialize managed return type }
n := Length(text);
{ dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid }
SetLength(dp, n + 1);
SetLength(valid, n + 1);
valid[0] := True; { empty prefix is valid }
for i := 1 to n do
begin
valid[i] := False;
for j := 0 to i - 1 do
begin
{ Check whether dp[j] contains a valid split point;
if it does, it means the prefix text[0:j] can be segmented. }
if valid[j] then
begin
// Create a lightweight substring representing text[j:i].
len := i - j;
candidate := Copy(text, j + 1, len);
{ Convert the string_view to a std::string so it can be checked in the dictionary.
Then verify whether this substring is a valid dictionary word. }
if dict_contains(candidate, dict) then
begin
{ Record that index j is the previous valid split before i.
This means text[j:i] is a valid word and dp[j] was valid. }
dp[i] := j;
valid[i] := True;
{ Stop searching for other j values because we already found
a valid segmentation ending at i. }
Break;
end;
end;
end;
end;
{ If dp[n] is not valid, segmentation is impossible }
if not valid[n] then
begin
Exit; { Result is already initialized }
end;
{ Backtrack to recover words }
SetLength(words, n + 1);
count := 0;
i := n;
while i > 0 do
begin
j := dp[i];
len := i - j;
w := Copy(text, j + 1, len);
words[count] := w;
Inc(count);
i := j;
end;
{ Reverse the collected words }
for i := 0 to (count div 2) - 1 do
begin
tmp := words[i];
words[i] := words[count - 1 - i];
words[count - 1 - i] := tmp;
end;
{ Return results }
SetLength(words, count);
Result := words;
end;
var
text: string;
dict: array of string;
words: TStringArray;
i: Integer;
begin
text := 'thisisatestfoo';
{ Example dictionary }
dict := ['this', 'is', 'a', 'test', 'hello', 'world', 'foo', 'bar'];
{ Call the segmentation function }
words := segment_text(text, dict);
{ Print results }
WriteLn('Segmentation result:');
for i := 0 to High(words) do
WriteLn(words[i]);
end.
{
run:
Segmentation result:
this
is
a
test
foo
}
