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);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
동작 그만. 밑장 빼기냐? - 20519번 (0) | 2022.03.02 |
---|---|
강의실 배정 - 11000번 (0) | 2022.02.28 |
치킨 배달 - 15686번 (0) | 2022.02.23 |
아기 상어 - 16236번 (0) | 2022.02.23 |
감시 - 15683번 (0) | 2022.02.18 |