文本编辑问题

Question

我正在逐行遍历文本文件，调整文本，使文件最终符合在MIPS模拟器(MARS)上运行所需的语法。我的问题是，每当我看到一行中包含字符串"blezl“时，我想做几件事。首先，我需要在包含这个单词的行后插入一些文本行。使用insert很容易做到这一点。然后，我必须在最初找到的行之后的行后插入一些文本行。问题是，我需要在整个文档中搜索位于找到的字符串末尾的字符串，然后在包含找到的第二个字符串的任何行之前插入几行。所以..。

  #1 blezl v0,#10
  #2 addu s1,s0,s5
  #3 lw v1,0(s8)
  ...
  #10 addu s1,s0,s5

我需要找到"blezl"，然后在"#1“和"#2”之间插入一些行。然后我在"#2“和"#3”之间插入一些行，然后我需要在整个文档中搜索"#10“，当我找到任何行时，我会在它之前插入一些行。问题是，最后一步需要搜索整个文档(在逐行遍历文档的过程中，直到找到blezl )。这是因为"#10“可以出现在"#1”之前或之后的任何地方。这将永远耗费时间(我的文件中有80k行，其中可能有大约2%的行包含"blezl“)。我如何才能在没有大量冗余步骤的情况下做到这一点？

Answer 1

80k行还不够大，无法将其加载到RAM中。一旦在ram中有了数据，搜索就会变得相当快。

如果你关心性能，你可以制作一个b-tree来存储基于标签的行。这将为您提供需要查找的每一行的log(n)搜索时间。