찾기 - 1786번

---

 

KMP 알고리즘 문제

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String T = br.readLine();
        String P = br.readLine();
        int lenT = T.length();
        int lenP = P.length();

        int[] arr = new int[P.length()];    // 부분일치 테이블 (접미사, 접두사가 같은 최대 크기)
        int count = 0;
        StringBuilder sb = new StringBuilder();

        int index = 0;

        // 테이블 만들기
        for (int i = 1; i < lenP; i++) {
            // 다르면 index 를 앞으로 당김 (이전에 동일한 부분 찾음)
            while (index > 0 && P.charAt(i) != P.charAt(index)) {
                index = arr[index - 1];
            }
            // 같으면 index + 1 만큼 동일, 최대크기 입력후 index 도 1증가 
            if (P.charAt(i) == P.charAt(index)) {
                arr[i] = ++index;
            }
        }
        // 패턴 포인터
        index = 0;
        
        // i = 텍스트 포인터
        for (int i = 0; i < lenT; i++) {
            // 다르면 index 를 앞으로 당김 (이전에 동일한 부분 찾음)
            while (index > 0 && T.charAt(i) != P.charAt(index)) {
                index = arr[index - 1];
            }
            // 현재 가르키는 포인터에 있는 글자 일치
            if (T.charAt(i) == P.charAt(index)) {
                // 패턴 포인터가 마지막이면 
                if (index + 1 == lenP) {
                    sb.append(i - index + 1).append(" ");   // 현재 인덱스 위치 추가
                    count++;                // 갯수 counting
                    index = arr[index];     // index 를 이전 동일한 부분으로 변경 
                } else {
                    // 패턴 포인터가 마지막이 아니면 다음 확인
                    index++;
                }
            }
        }

        System.out.println(count);
        System.out.println(sb);
    }
}