C#递归实现多轮$字符替换N过大内存溢出问题求优化方案

• 递归栈溢出：当N值较大时，递归调用的层数过多，会直接触发栈溢出错误。
• 字符串指数膨胀：假设固定模式串P中有k个$，每执行一次替换，字符串长度就会变为 (P.Length - k) + k * 上一轮字符串长度，N稍大时字符串长度会突破内存上限，完全无法完整存储。
• 不必要的全量生成：你代码中读取了MIN、MAX参数，说明你仅需要最终字符串的指定区间字符，完全没必要生成整个超长大字符串。
• 写法不规范：你将递归函数写在Main方法内，捕获外部的N变量，属于非规范的闭包用法，也会增加额外的内存开销。

方案1：迭代生成全量字符串（仅适合N<10的小场景） #

把递归改为迭代，解决栈溢出问题，写法更规范：

using System;

namespace SZTF1HF_new {
  class Program {
    static void Main(string[] args) {
      string S = Console.ReadLine();
      string P = Console.ReadLine();
      int N = int.Parse(Console.ReadLine());
      int MIN = int.Parse(Console.ReadLine());
      int MAX = int.Parse(Console.ReadLine());

      string current = S;
      for (int i = 0; i < N; i++)
      {
          current = P.Replace("$", current);
      }
      
      // 输出指定区间
      Console.WriteLine(current.Substring(MIN, MAX - MIN + 1));
    }
  }
}

该方案仅解决递归栈溢出问题，无法处理大N场景，N超过10后大概率还是会内存不足。

方案2：按需提取指定区间字符（大N场景最优） #

不需要生成完整字符串，倒推每个目标位置对应的原始字符，内存占用极低，时间复杂度仅和MIN到MAX的区间长度成正比：

using System;
using System.Text;
using System.Linq;

namespace SZTF1HF_new {
  class Program {
    static void Main(string[] args) {
      string S = Console.ReadLine();
      string P = Console.ReadLine();
      int N = int.Parse(Console.ReadLine());
      int MIN = int.Parse(Console.ReadLine());
      int MAX = int.Parse(Console.ReadLine());
      
      int dollarCountInP = P.Count(c => c == '$');
      
      // 预计算每一层替换后的字符串长度，超过MAX就不用精确计算，避免溢出
      long[] layerLength = new long[N + 1];
      layerLength[0] = S.Length;
      for (int i = 1; i <= N; i++)
      {
          long nextLen = (P.Length - dollarCountInP) + dollarCountInP * layerLength[i - 1];
          layerLength[i] = nextLen > MAX + 1 ? MAX + 1 : nextLen;
      }
      
      // 递归查询指定位置的字符，层数是当前替换轮次
      char GetCharAt(long pos, int layer, string currentPattern)
      {
          if (layer == 0)
          {
              return S[(int)pos];
          }
          long offset = 0;
          foreach (char c in currentPattern)
          {
              if (c != '$')
              {
                  if (offset == pos) return c;
                  offset++;
              }
              else
              {
                  long subLen = layerLength[layer - 1];
                  if (pos < offset + subLen)
                  {
                      return GetCharAt(pos - offset, layer - 1, S);
                  }
                  offset += subLen;
              }
          }
          throw new ArgumentOutOfRangeException(nameof(pos));
      }
      
      StringBuilder result = new StringBuilder();
      for (long p = MIN; p <= MAX; p++)
      {
          result.Append(GetCharAt(p, N, P));
      }
      Console.WriteLine(result.ToString());
    }
  }
}

该方案哪怕N达到上百，只要MIN到MAX的区间长度在几千以内，都不会有内存不足问题。

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