C# 배열 서브 세트 페치

Question

바이트 배열이 있으며이 바이트 배열의 내용이 다른 더 큰 배열 내에 연속 시퀀스로 존재하는지 확인하고 싶습니다. 이 작업을 수행하는 가장 간단한 방법은 무엇입니까?

Answer 1

순진한 접근법은 다음과 같습니다.

public static bool IsSubsetOf(byte[] set, byte[] subset) {
    for(int i = 0; i < set.Length && i + subset.Length <= set.Length; ++i)
        if (set.Skip(i).Take(subset.Length).SequenceEqual(subset))
            return true;
    return false;
}

보다 효율적인 접근 방식을 위해서는 더 많은 고급 문자열 일치 알고리즘을 고려할 수 있습니다. KMP.

Answer 2

문자열 검색 알고리즘을 조정하십시오. 가장 빠른 것 중 하나입니다 보이어 모어 . 아주 쉽습니다. 이진 데이터의 경우 Knuth-Morris-Pratt 알고리즘도 매우 효율적으로 작동 할 수 있습니다.

Answer 3

이것은이 답의 1/1 포트입니다. Java가있는 이진 파일에서 일련의 바이트 검색

그렇게하는 매우 효율적인 방법입니다.

public static class KmpSearch {

    public static int IndexOf(byte[] data, byte[] pattern) {
        int[] failure = ComputeFailure(pattern);

        int j = 0;
        if (data.Length == 0) return -1;

        for (int i = 0; i < data.Length; i++) {
            while (j > 0 && pattern[j] != data[i]) {
                j = failure[j - 1];
            }
            if (pattern[j] == data[i]) { j++; }
            if (j == pattern.Length) {
                return i - pattern.Length + 1;
            }
        }
        return -1;
    }


    private static int[] ComputeFailure(byte[] pattern) {
        int[] failure = new int[pattern.Length];

        int j = 0;
        for (int i = 1; i < pattern.Length; i++) {
            while (j > 0 && pattern[j] != pattern[i]) {
                j = failure[j - 1];
            }
            if (pattern[j] == pattern[i]) {
                j++;
            }
            failure[i] = j;
        }

        return failure;
    }
}