文本編輯問題

Question

我正在逐行調整文本遍歷文本文件，以便文件最終將匹配在MIPS模擬器（MARS）上運行所需的語法。我的問題是，每當我看到一行字符串「blezl」時，我想做幾件事情。首先，我需要在包含這個單詞的行後面插入一些文本行。這很容易使用插入。然後，我必須在最初跟在找到的行後面的行之後插入一些文本行。問題是，我需要在整個文檔中搜索找到的字符串末尾的字符串，然後在包含找到的第二個字符串的行之前插入幾行。所以..

#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」，當我找到它時，我在它之前插入一些行。問題在於最後一步需要搜索整個文檔（在逐行遍歷的中間，直到找到bl​​ezl）。這是因爲「＃10」可能發生在「＃1」之前或之後的任何地方。這將會持續下去（我的文件中有8萬行，大概有2％的文件中有「blezl」）。我如何在沒有大量冗餘步驟的情況下做到這一點？

Answer 1

80k行不夠大，無法將其加載到RAM中。一旦你有RAM中的數據，搜索速度相當快。

如果您關心性能，可以製作一棵b-tree來存儲基於標籤的行。這會給你每個需要查找的行的日誌（n）搜索時間。