txt 파일에서 길이가 L 인 특정 문자열을 찾음

Question

y{N}y{N-1}...y{1} 형태의 길이가 N 인 y이 있다고 가정합니다. 그런 다음 길이가 L (L보다 작은 L) 인 또 다른 16 진수 문자열 x이 주어진다면이 문자열이 y 안에 몇 번이나 나타나는지 확인하고 싶습니다. y{N}...x{L}x{L-1}...x{1}...y{j}..x{L}x{L-1}...x{1}....y{1}과 같이 말하십시오. C에서이 작업을 수행하는 가장 효율적인 방법은 무엇입니까? ... 큰 데이터베이스에서이 작업을 실행하려면 실제로 효율적인 구현이 필요합니다.

Answer 1

요청은 단순한 string search algorithm입니다. 이를 수행 할 알고리즘이 많이 있습니다. 대부분은 전처리를 통해 O (L + N)에서 좋은 답을 줄 것입니다.

suffix tree을 사용하면 O (L + Z)에서 더 빠른 답변을 제공 할 수 있습니다. 여기서 Z는 y에서 x가 나오는 횟수입니다. 접미사 트리는 많은 메모리 공간을 차지하지만 (O (N²)), 이상적인 선택이 아닐 수도 있습니다.

Answer 2

"16 진수"는 여기 의미하는 것이 아닙니다. C++는 컴퓨터 언어이며 비트로 작동합니다. "16 진수"는 인간 소비를 위해 4 비트를 함께 그룹화하는 편리한 방법입니다.

마찬가지로 C++에서는 y{N}y{N-1}...y{1}과 같은 문자열을 인덱싱하지 않습니다. 그것들을 y[0],y[1],y[N-1]으로 색인합니다. (y[N]은 없습니다.)

정상적인 상황에서는 std::string::find이 디스크보다 빠르며 빠르다는 것을 의미합니다.

Answer 3

C++에서 가장 효율적인 방법은 무엇입니까?

에 한번이처럼 입력 파일의 std::istream_iterator에서 std::search : 그 빠른 충분하지 않으면

#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을 시도 할 수 있습니다.

이 빠르지 않으면 파일을 메모리 매핑하고 이터레이터로 초기 및 최종 포인터를 사용해보십시오.