[백준/JAVA] 16916번: 부분 문자열

🔺 문제

16916번: 부분 문자열

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] pi; // 패턴 일치 저장 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String S = br.readLine();
        String P = br.readLine();
        
        makePi(P);    
        System.out.println(KMP(S, P));
    }
    
    // 패턴 일치 저장 배열
    public static void makePi(String pattern) {
        pi = new int[pattern.length()];
        
        int idx = 0;
        for(int i = 1 ; i < pattern.length() ; i++) {
            // idx > 0 : 문자열 매칭 시작
            // 연속으로 일치하지 않으면, j-1칸의 공통 부분 위치로 이동
            while(idx > 0 && pattern.charAt(i) != pattern.charAt(idx)) {
                idx = pi[idx - 1];
            }
            
            // 맞는 경우
            if(pattern.charAt(i) == pattern.charAt(idx)) {
                // i 길이 문자열의 공통 길이 = j의 위치 + 1
                idx++;
                pi[i] = idx;
                
                // == pi[i] = ++idx;
            }
        }
    }
    
    // 문자열 매칭
    public static int KMP(String str, String pattern) {
        int idx = 0;    // 패턴 내 일치 체크 idx
        
        for(int i = 0 ; i < str.length() ; i++) {
            // 맞는 위치가 나올 때까지 j-1칸의 공통 부분 위치로 이동
            while(idx > 0 && str.charAt(i) != pattern.charAt(idx)) {
                idx = pi[idx - 1];
            }
            
            // 맞는 경우
            if(str.charAt(i) == pattern.charAt(idx)) {
                if(idx == pattern.length() - 1) {   // 패턴 끝까지 확인했으면 정답
                    idx = pi[idx];
                    return 1;
                }
                else {  // 맞았지만, 패턴이 끝나지 않았다면 패턴의 다음 문자 확인
                    idx++;
                }
            }
        }
        return 0;
    }
}

✅ 해결 아이디어
✔ KMP 문자열 매칭 알고리즘

과정 설명은 타 블로그에서 너무 잘 하셔서 그거 보는 게 더 좋을 듯...

(밑에 참고 링크 남김)

 

---

💬 느낀 점

오...

사실 contains 쓸 수도 있지만

KMP 뼈대문제라고 하셔서

KMP 알고리즘 배우고 다른 분 코드 보고 작성했다.

 

KMP 책에서는 못 보고 처음 보고 이해하느라 시간이 좀 걸렸다...만

앞으로 자주 쓰고 익숙해지면 좋겠따...!

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 감격적인 과정 설명...ㅠㅠㅠ 덕분에 KMP알고리즘을 이해했다... (복습용!)

[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘

 

[알고리즘] 문자열 매칭 알고리즘 KMP (Java)

[알고리즘] 문자열 검색 알고리즘 KMP 자바 구현하기 (백준 16916)

 

 

✔ 풀이 참고

[알고리즘] 문자열 검색 알고리즘 KMP 자바 구현하기 (백준 16916)