문자열 검색 알고리즘 - 일치하는 문자열의 복잡성

Question

내가'문자열 검색 알고리즘'에 대한 해결하기 위해 노력하고 있지만, 많은 사이트의 답변 O (m 복잡한 ('나이브 문자열 검색' 것 같다 (N- KMP도 O (n)이 따라서 확실히 잘못된이어야 가지고 있지만 어디?

동안 아래에있는 내 너 한테의 문제 무엇 m + 1))은, 그것은, O (N)의 최악의 복잡도를 갖는다

def find(s1, s2): 
    size = len(s1) 
    index = 0 
    while (index != len(s2)): 
     if s2[index : index + size] == s1: 
      print 'Pattern found at index %s'%(index) 
      index += size 
     else: 
      index += 1 

그래, 내가 s2[index : index + size] == s1이 O라고 가정하고 있었다. (1)은 O (n)이므로 이제는 원래의 질문이됩니다.

• 두 문자열의 해시가 계산되고 비교되지 않는 이유는 두 해시가 같은 문자열이어야한다는 것입니다.
• 어떻게 충돌 할 수 있는지 모르겠다. 그 해시 알고리즘에 의존하지 않습니다. MD5에는 알려진 휴식 시간이 있습니다.

Answer 1

원래의 질문에

난 당신의 코드 복잡도 O (N)를 가지고 있다고 생각하지 않지만 오히려 O (백만). 이 검사는 s2[index : index + size] == s1입니다. 왜냐하면 최악의 경우 문자 비교를 len(s1) 번 수행해야하기 때문입니다. 해싱

---

여기 Wikipedia's definition of a hash function 같습니다

해시 함수는 고정 된 크기의 데이터 임의의 사이즈의 데이터를 매핑하는데 사용될 수있는 기능이다. 해시 함수에 의해 반환 된 값을 해시 값, 해시 코드, 다이제스트 또는 단순히 해시라고합니다. 한 가지 용도는 빠른 데이터 조회를 위해 컴퓨터 소프트웨어에서 널리 사용되는 해시 테이블이라고하는 데이터 구조입니다.

여기서 우리는이 접근법의 첫 번째 문제에 봉착하게됩니다. 해쉬 함수는 임의의 크기의 값을 취해 고정 된 크기의 값을 반환합니다. pigeonhole principle 다음에 여러 값이 포함 된 해시가 하나 이상 있습니다. 빠른 예제로서 해시 함수가 항상 1 바이트 길이의 출력을 생성한다고 가정합니다. 이는 가능한 256 개의 출력이 있음을 의미합니다. 257 개의 항목을 해시 한 후에는 동일한 해시가있는 항목이 2 개 이상 있는지 항상 확실합니다. 이것을 가능한 한 오랫동안 피하기 위해 좋은 해시 함수는 모든 가능한 출력에 대한 입력을 가능한 한 uniformly으로 매핑합니다.

해시가 같지 않은 경우 문자열이 동일하지는 않지만 그 반대는 아닌지 확인할 수 있습니다. 두 개의 다른 문자열은 동일한 해시를 가질 수 있습니다.