查找txt文件中長度爲L的特定字符串的出現

-1

假設我有一個長度爲N的十六進制字符串y，其格式爲y{N}y{N-1}...y{1}。然後給出另一個長度爲L（L小於N）的十六進制字符串x，我想檢查這個字符串出現在y之內多少次（如果有的話），比如說y{N}...x{L}x{L-1}...x{1}...y{j}..x{L}x{L-1}...x{1}....y{1}。哪一個是最有效的方式來做到這一點在C++？...我需要一個非常有效的實現，因爲我想運行這個大型數據庫查找txt文件中長度爲L的特定字符串的出現

來源

2012-09-24 Hashed

這是如此不清楚......你能發表現實生活中的例子嗎？ –

查看['strstr']（http://pubs.opengroup.org/onlinepubs/009695399/functions/strstr.html）或['std :: string :: find']（http：//en.cppreference。 COM/W/CPP /串/ basic_string的/發現）。循環調用。 –

我想計算十六進制說1111出現在「較大」十六進制內的次數（例如，如果數字是8366461111，那麼這會出現一次，如果54641111456411114342那麼它出現兩次）。我希望我現在更清晰 – Hashed

您的請求是一個簡單的string search algorithm。有很多算法可以做到這一點。大多數人會在O（L + N）的預處理中給你一個很好的答案。

你也可以使用一個suffix tree這將在O（L + Z）中提供更快的答案，其中Z是y中x的出現次數。雖然後綴樹佔用大量內存空間（O（N²）），但在這裏可能不是理想的選擇。

來源

2012-09-24 11:19:12

「十六進制」在這裏並不意味着什麼。 C++是一種計算機語言，適用於位。「十六進制」只是將4位組合在一起供人類消費的便利方式。

同樣，C++不索引字符串，如y{N}y{N-1}...y{1}。它將它們索引爲y[0],y[1],y[N-1]。（沒有y[N]。）

在正常情況下，std::string::find會比你的磁盤快，這意味着它足夠快。

來源

2012-09-24 11:20:42 MSalters

哪一種方式在C++中最有效？

嘗試std::search在您輸入文件的std::istream_iterator，像這樣：

#include <string> 
#include <iterator> 
#include <iostream> 
#include <algorithm> 

int main() { 
    // std::ifstream input("input.txt"); 
    std::istream& input(std::cin); 
    std::string search_for("1234"); 

    std::istream_iterator<char> last; 
    std::istream_iterator<char> it(input); 
    int count(0); 

    while((it = std::search(it, last, search_for.begin(), search_for.end())) != last) { 
    count++; 
    } 

    std::cout << count << "\n"; 

}

如果不夠快，你可以嘗試std::istreambuf_iterator。

如果速度不夠快，您可以嘗試內存映射文件並使用初始指針和最終指針作爲迭代器。

來源

2012-09-24 15:10:28

查找txt文件中長度爲L的特定字符串的出現

回答

相關問題