[백준, 16916번] 부분 문자열 (KMP, Java)

 

문제설명

입력 & 출력

잘못된 풀이

1. charAt() 메서드 사용

public class BOJ16916 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String P = br.readLine();

        boolean isSubString = false;

        for (int i = 0; i <= S.length() - P.length(); i++) {
            isSubString = true;
            for (int j = 0; j < P.length(); j++) {
                if(S.charAt(i + j) != P.charAt(j)){
                    isSubString = false;
                    break;
                }
            }
            if (isSubString) break;
        }
        System.out.println(isSubString ? 1 : 0);
    }
}

2. contains() 메서드 사용

public class BOJ16916 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String P = br.readLine();

        // S가 P를 포함하고 있다면 1을 출력, 아니면 0을 출력
        System.out.println(S.contains(P) ? 1 : 0);
    }
}

 

 

이번 문제는 문자열 2개가 주어졌을 때 P가 S의 부분 문자열이면 1, 아니면 0을 출력하는 간단한 문제입니다.

 

그런데 기본 부분 문자열 알고리즘을 사용한다면 간단하지만 최악의 경우 O(n*m)의 시간 복잡도를 가지기 때문에 더 효율적인 문자열 매칭 알고리즘인 KMP알고리즘을 사용해야합니다.

[Algorithm] KMP(Knuth-Morris-Pratt) 알고리즘이란 무엇일까❓ (문자열 비교)

 

 

나의 풀이

전체 풀이

---

main 문

 

먼저 main문에서는 BufferedReader를 사용하여 입력을 받아줍니다.

 

pi 배열 생성 함수

 

KMP 알고리즘을 사용하기 위해서는 중복된 접두사와 접미사 정보를 미리 계산한 배열인 pi 배열을 생성해야 합니다.

 

pi 배열은 각 인덱스까지의 부분 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하여 생성할 수 있습니다.

 

최대 길이를 저장할 변수 len을 초기화해주고, pi배열의 0번째 값은 항상 0이기 때문에 1번째 부터 패턴의 길이만큼 반복문을 돌려줍니다.

 

최대길이 len이 0인 경우에는 접근을 하지 못하도록 len > 0 조건과 패턴과 문자열을 비교한 후 값이 다르다면 최대 길이를 Miss Match한 문자의 전 정보를 가져오고, 다시 탐색을 하기위해서 len - 1로 길이를 조정해 이전 최대 길이로 돌아가 다시 비교합니다.

 

이 과정을 문자열과 패턴이 같을 때 까지 while문을 통해 계속 체크해줍니다. 그리고 만약 값이 같다면, 최대 길이 len을 늘려주고, pi 배열의 값을 최대 길이로 채워줍니다.

 

 

KMP

 

KMP 메서드는 주어진 문자열 str에서 특정 패턴 pattern이 존재하는지 확인합니다.

1. pi 배열 초기화
   • pi_array 메서드를 통해 pattern의 pi 배열을 미리 계산해 중복되는 접두사와 접미사를 처리할 준비를 합니다.
2. 문자열 탐색
   • idx를 0으로 초기화하고, str의 각 문자에 대해 pattern과 비교합니다.
   • 만약 str의 현재 문자와 pattern의 현재 문자가 일치하지 않으면 pi 배열을 이용해 idx를 조정합니다.
   • 문자가 일치할 경우 idx를 증가시킵니다.
3. 패턴 일치 확인
   • idx가 pattern의 길이에 도달하면 패턴이 존재한다는 뜻으로 true를 반환합니다. 그렇지 않으면 끝까지 검사 후 false를 반환합니다.

동작 과정

• 입력 

baekjoon
joo

 

• pi 배열 생성
  • [0, 0, 1]
• 문자열 탐색

i	str.charAt(i)	idx	설명
0	'b'	idx = 0	"b"는 pattern의 첫 문자와 불일치, idx는 그대로
1	'a'	idx = 0	"a"는 pattern의 첫 문자와 불일치, idx는 그대로
2	'e'	idx = 0	"e"는 pattern의 첫 문자와 불일치, idx는 그대로
3	'k'	idx = 0	"k"는 pattern의 첫 문자와 불일치, idx는 그대로
4	'j'	idx = 1	"j"는 pattern의 첫 문자와 일치, idx 증가 -> 1
5	'o'	idx = 2	"o"는 pattern의 두 번째 문자와 일치, idx 증가 -> 2
6	'o'	idx = 3 (pattern.length)	"o"는 pattern의 첫 문자와 일치, idx가 pattern 길이에 도달(3)했으므로 true 반환