Rabin-Karp 알고리즘을 사용한 패턴 검색용 PHP 프로그램

Rabin-Karp 알고리즘이란 무엇인가요?

Rabin-Karp 알고리즘은 더 큰 텍스트에서 패턴 발생을 효율적으로 검색하는 문자열 패턴 일치 알고리즘입니다. 1987년 Michael O. Rabin과 Richard M. Karp가 개발했습니다.

이 알고리즘은 해싱 기술을 활용하여 패턴과 텍스트 하위 문자열의 해시 값을 비교합니다. 작동 방식은 다음과 같습니다.

• 패턴과 텍스트의 첫 번째 창의 해시 값을 계산합니다.

• 패턴을 텍스트 위로 한 번에 한 위치씩 밀어 넣고 해시를 비교하세요.

• 해시가 일치하면 패턴의 문자와 현재 텍스트 창을 비교하여 일치 여부를 확인하세요.

• 일치하는 것이 있으면 일치하는 위치/인덱스를 기록하세요.

• 롤링 해시 함수를 사용하여 다음 텍스트 창의 해시를 계산합니다.

• 텍스트의 모든 위치가 확인될 때까지 3~5단계를 반복하세요.

롤링 해시 기능은 이전 창에서 첫 번째 문자의 기여도를 빼고 새 창의 다음 문자의 기여도를 더하여 각 새 창의 해시 값을 효과적으로 업데이트합니다. 이렇게 하면 각 창에 대해 처음부터 해시를 다시 계산하는 것을 방지하여 알고리즘을 더욱 효율적으로 만들 수 있습니다.

패턴 검색을 위한 Rabin-Karp 알고리즘용 PHP 프로그램

출력

코드 설명

PHP 코드는 패턴 검색을 위해 Rabin-Karp 알고리즘을 구현합니다. 패턴과 텍스트를 입력으로 사용하고 텍스트에서 패턴이 발생하는지 검색합니다. 이 알고리즘은 패턴과 텍스트의 첫 번째 창의 해시 값을 계산합니다. 그런 다음 현재 창의 해시와 패턴을 비교하여 텍스트 위로 패턴을 슬라이드합니다. 해시가 일치하면 문자가 하나씩 추가로 확인됩니다. 일치하는 항목이 발견되면 패턴이 발견된 인덱스를 인쇄합니다. 알고리즘은 롤링 해시 함수를 사용하여 각 창의 해시 값을 효율적으로 업데이트합니다. 이 코드는 "ABCABCABCABCABCABC" 텍스트에서 "BC" 패턴을 검색하여 알고리즘을 사용하는 방법을 보여줍니다.

결론

요약하자면, PHP 프로그램은 패턴 검색을 위한 Rabin-Karp 알고리즘을 효과적으로 구현합니다. 롤링 해시 함수를 활용하고 해시 값을 비교함으로써 알고리즘은 더 큰 텍스트에서 패턴 발생을 효율적으로 검색할 수 있습니다. 프로그램은 텍스트에서 발견된 패턴의 인덱스를 올바르게 식별하고 결과를 출력합니다. 명확한 구조와 적절한 해시 계산을 통해 이 프로그램은 PHP의 패턴 검색을 위한 Rabin-Karp 알고리즘의 강력함과 유용성을 보여줍니다.

위 내용은 Rabin-Karp 알고리즘을 사용한 패턴 검색용 PHP 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!