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

라빈-카프 알고리즘이란 무엇인가요?

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!