simDev1234
심플하고 차분하게
simDev1234
전체 방문자
오늘
어제
  • 분류 전체보기
    • Computer Science
      • Basic Math
      • Data Structure
      • Algorithm
      • Database
      • OS
    • Language
      • Java
      • Kotlin
      • SQL
    • Framework
      • Spring
      • Orm&Mapper
      • 프로젝트로 스프링 이해하기
      • 스프링 라이브러리
    • Infra
      • Cloud
      • Docker
      • Redis
      • AWS, Azure
      • Device
    • Etc
      • CleanCoding
    • Git,Github

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 자바프로그래밍
  • 자바
  • 404
  • JVM메모리구조
  • null
  • scanner #next() #nextLine()
  • 컨트롤러
  • controllerTest
  • 자바메모리구조
  • 참조변수
  • 참조타입
  • 자바프로그램
  • 스프링

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
simDev1234
Computer Science/Algorithm

문자열 알고리즘 - KMP와 Robin-Karp 알고리즘

Computer Science/Algorithm

문자열 알고리즘 - KMP와 Robin-Karp 알고리즘

2022. 10. 13. 17:46

|  관련 강의 영상

https://www.youtube.com/watch?v=UcjK_k5PLHI 

- KMP나 Robin-Karp를 사용하면 O(n)의 시간복잡도로 문자열에서 패턴 문자열을 찾을 수 있다.

- KMP는 어려워서 일단 Robin-karp 부분만 찾아서 적용해보았다.

 

|  Robin-Karp 알고리즘 사용해보기

https://joomn11.tistory.com/111?category=900637 

 

[알고리즘] 라빈 카프(Rabin-Karp)(문자열 탐색)(Rolling Hash)

문자열 탐색 알고리즘 Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다. 문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은

joomn11.tistory.com

public static int robinKarp(String parent, String pattern, int parentSize, int patternSize){

    int parentHash = 0, patternHash = 0, power = 1;
    int result = 0;

    // 슬라이딩 윈도우 방식으로 하나씩 증가
    for (int i = 0; i <= parentSize - patternSize; i++) {
        // 처음에는, 패턴 문자열 길이만큼 해시값을 구한다.
        if (i == 0) {
            for (int j = 0; j < patternSize; j++) {
                parentHash += parent.charAt(j) * power;
                patternHash += pattern.charAt(j) * power;
            }

            if (i < patternSize - 1) {
                power *= 2;
            }
        } 
        // 처음이 아닌 경우, 가장 앞의 문자를 빼고, 새로운 문자를 추가한다.
        else {
            parentHash = (parentHash - parent.charAt(i - 1) * power) * 2
                    + parent.charAt(i + patternSize - 1);
        }

        // 윈도우 위치에서 부모와 패턴이 일치하는 경우
        if (parentHash == patternHash) {
            result++;
        }
    }

    return result;
}

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 속도 구하기  (0) 2022.09.29
[알고리즘] 최소신장트리(MST)  (0) 2022.09.01
[알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘  (0) 2022.09.01
[알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드  (0) 2022.09.01
[알고리즘] 최단 경로 구하기 - 1. 다익스트라  (0) 2022.09.01
  • |  관련 강의 영상
  • |  Robin-Karp 알고리즘 사용해보기
'Computer Science/Algorithm' 카테고리의 다른 글
  • 알고리즘 속도 구하기
  • [알고리즘] 최소신장트리(MST)
  • [알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘
  • [알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드
simDev1234
simDev1234
TIL용 블로그. * 저작권 이슈가 있는 부분이 있다면 댓글 부탁드립니다.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.