'문자열' 태그의 글 목록

'문자열'에 해당되는 글 1건

2017.12.21 java 로 KMP 알고리즘

java 로 KMP 알고리즘

[프로그래밍] 2017. 12. 21. 21:43

import java.util.ArrayList;
import java.util.List;

public class KMP {

private String string;

private String pattern;

/**
     * 길이가 N 인 문자열 S(string) 에서 길이가 M 인 문자열 P(pattern) 를 탐색한다.<br/>
     * 시간복잡도는 O(N+M) 이다.<br/>
     *
     * @param string  원본 문자열
     * @param pattern 찾을 문자열
     */
    public KMP(String string, String pattern) {
        this.string = string;
        this.pattern = pattern;
    }

public void setString(String string) {
        this.string = string;
    }

public void setPattern(String pattern) {
        this.pattern = pattern;
    }

/**
     * @return 문자열이 일치하는 index 의 배열
     */
    public List<Integer> search() {
        List<Integer> searchIndex = new ArrayList<>();

char[] s = string.toCharArray();
        char[] p = pattern.toCharArray();
        int[] pi = getPI();
        int n = string.length();
        int m = pattern.length();
        int j = 0;

for (int i = 0; i < n; i++) {
            while (j > 0 && s[i] != p[j]) {// j > 0 : 한 글자 라도 일치한 것이 있는지
                j = pi[j - 1];
            }
            if (s[i] == p[j]) {
                if (j == m - 1) {
                    searchIndex.add(i - m + 1);
                    j = pi[j];
                } else {
                    j++;
                }
            }
        }

return searchIndex;
    }

/**
     * 탐색 실패 시 i번째까지 일치 할 경우 몇글자를 건너뛰어야 하는지 알려주는 pi 배열을 구한다.<br/>
     * pi 배열을 구할 때도 search 방식을 적용하여 O(M) 의 시간복잡도를 갖는다.<br/>
     *
     * @return pi 배열
     */
    public int[] getPI() {
        int m = pattern.length();
        int j = 0;
        char[] p = pattern.toCharArray();
        int[] pi = new int[m];

for (int i = 1; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = pi[j - 1];
            }
            if (p[i] == p[j]) {
                pi[i] = ++j;
            }
        }

return pi;
    }
}

저작자표시 변경금지

'[프로그래밍]' 카테고리의 다른 글

오늘부터의 목표 (0)	2022.07.18
Apache Ratis 소개 (3)	2018.03.21
dfs 알고리즘을 java 로 구현하기 (0)	2017.02.16
[IntelliJ] SVN 커밋 시 'is out of date' 에러 문제 (0)	2015.10.23
rsync 로 CRAN mirroring (0)	2015.10.06

Posted by FeliZ_하늘..

이전 1 다음

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

왕초보 프로그래머 Sky

'문자열'에 해당되는 글 1건

java 로 KMP 알고리즘

'[프로그래밍]' 카테고리의 다른 글

카테고리

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크

티스토리툴바