如何优化Delphi字符串区间字符统计程序的运行时长？

原程序的性能瓶颈在于每次查询都需要复制子串并遍历计数，当查询次数多或区间跨度大时，时间复杂度会达到O(n*k)（n为查询次数，k为区间平均长度），导致运行超时。以下是几种可行的优化方法：

1. 前缀和数组预处理（最优方案） #

针对所有可能的Ansi字符（共256种）提前构建前缀和数组，将单次查询的时间复杂度降到O(1)，整体时间复杂度优化为O(m + n)（m为字符串长度，n为查询次数）。

实现思路： #

• 定义一个二维数组prefix[0..255, 0..m]，其中prefix[Ord(c), i]表示原字符串前i个字符中字符c的出现次数。
• 遍历原字符串完成预处理：每个位置i，继承前i-1位的计数，再对当前字符的计数加1。
• 查询时直接用区间尾部的计数减去区间头部前一位的计数，即可得到结果。

示例代码： #

uses SysUtils;
var
  stringlength, querynum, i, start, tail: Int64;
  input: AnsiString;
  querychar: Char;
  prefix: array of array of Int64; // 动态数组避免栈溢出
begin
  Readln(stringlength, querynum);
  Readln(input);
  
  // 初始化动态前缀和数组：256个字符，长度为stringlength+1（0到stringlength）
  SetLength(prefix, 256, stringlength + 1);
  for i := 0 to 255 do
    prefix[i, 0] := 0;
  
  // 预处理前缀和
  for i := 1 to stringlength do
  begin
    // 复制前一位的计数
    for var j := 0 to 255 do
      prefix[j, i] := prefix[j, i-1];
    // 当前字符计数+1
    Inc(prefix[Ord(input[i]), i]);
  end;
  
  // 处理查询
  for i := 1 to querynum do
  begin
    Readln(querychar, start, tail);
    Writeln(prefix[Ord(querychar), tail] - prefix[Ord(querychar), start - 1]);
  end;
end.

2. 移除子串复制操作（轻量优化） #

如果不想做全字符预处理，至少可以去掉Copy生成子串的步骤，直接遍历原字符串的目标区间计数，省去子串复制的内存分配与拷贝开销。这种方法虽然单次查询仍为O(k)，但能减少额外的性能损耗。

修改后的查询代码片段： #

// 替换原查询逻辑
cnt := 0;
for j := start to tail do
  if input[j] = querychar then Inc(cnt);
Writeln(cnt);

3. 按字符分组批量处理（特殊场景优化） #

如果所有查询可以一次性全部读取，可以将查询按目标字符分组，然后遍历一次原字符串，同时统计每组查询的区间计数。这种方法适用于查询可批量获取的场景，能进一步减少遍历次数。

内容的提问来源于stack exchange，提问作者user1039203