백준 16172번 나는 친구가 적다 (JAVA)

https://www.acmicpc.net/problem/16172

16172번: 나는 친구가 적다 (Large)

 

저는 해당 문제를 KMP를 이용하여 문제를 해결하였습니다.

일단 먼저 입력받을 것에서 숫자를 제거한 문자열을 kmp알고리즘을 사용하여 같은지를 확인하였습니다.

KMP 알고리즘은 접두사와 접미사를 비교하여 얼마나 같은지를 체크하고 불일치하면 점프해서 같은 부분들은 비교하지 않는 알고리즘입니다.

 

package BOJ.String;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_16172 {
    private static String deleteNum(String text){
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < text.length() ; i++){
            char now = text.charAt(i);
            if( (now >= 'a' && now <= 'z') || (now>='A' && now <= 'Z') ){
                sb.append(now);
            }
        }
        return sb.toString();
    }
    private static int kmp(String textString,String patternString){
        int tLength = textString.length();
        int pLength = patternString.length();
        char[] text = textString.toCharArray();
        char[] pattern = patternString.toCharArray();
        int[] fail = new int[pLength];

        int j = 0 ;
        for(int i = 1 ; i < pLength ; i++){
            while(j > 0 && pattern[i] != pattern[j]){
                j = fail[j-1];
            }
            if(pattern[i] == pattern[j]){
                fail[i] = ++j;
            }
        }
        j = 0;
        for(int i = 0 ; i < tLength ; i++){
            while(j > 0 && text[i] != pattern[j]){
                j = fail[j-1];
            }
            if(text[i] == pattern[j]){
                if(j == pLength-1){
                    return 1;
                }else{
                    j++;
                }
            }
        }
        return 0;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text = br.readLine();
        String pattern = br.readLine();
        System.out.println(kmp(deleteNum(text),pattern));
    }
}

 

참고

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&referrerCode=0&searchKeyword=KMP

30. KMP(Knuth-Morris-Pratt) 알고리즘