KMP 베이스 코드
import java.io.*;
import java.util.*;
// 본문에서 패턴이 몇 번 등장하는지 횟수와 등장한 위치들 출력
public class KMP {
static BufferedReader br;
static StringTokenizer st;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
char[] text = br.readLine().toCharArray();
char[] pattern = br.readLine().toCharArray();
int tLength = text.length;
int pLength = pattern.length;
int []pi = new int[pLength]; // 부분 일치 테이블(실패 함수)만들기 : 패턴 불일치가 발생할 경우 활용해서 패턴 포인터 이동 목적
for(int i=1, j=0; i < pLength; i++) { // 패턴에서 패턴을 찾는 원리 이용
// i: 패턴의 접미사, j: 패턴의 접두사
// 두 포인터 위치에서 불일치가 발생하면 맞은 위치의 정보를 활용해서 불필요한 비교를 줄임
while(j>0 && pattern[i] != pattern[j]) {
j = pi[j-1];
}
// 현재 i위치까지의 부분문자열의 접미사가 접두사와 일치하는 패턴의 최장길이 저장
if(pattern[i] == pattern[j]) {
pi[i] = j+1; // j위치까지 일치하는 경우 길이는 j+1, 후에 j 뒤로 이동
j++;
} else {
pi[i] = 0; // 일치하는 접두사 접미사 없음
}
}
System.out.println(Arrays.toString(pi));
int cnt = 0;
ArrayList<Integer> list = new ArrayList<>();
for(int i=0, j=0; i < tLength; i++) {
while(j>0 && text[i] != pattern[j]) {
j = pi[j-1];
}
if(text[i] == pattern[j]) {
if(j == pLength-1) { // 일치가 발생한 위치가 패턴의 끝이면
++cnt; // 패턴 찾았으므로 카운트 증가
list.add(i-j);
j = pi[j];
} else {
j++;
}
}
}
System.out.println(cnt);
if(cnt>0) {
System.out.println(list);
}
}
}
//ababababcababaca
//ababaca
//
//==>
//1
//[9]
//
//aaaaaab
//aaa
//
//==>
//4
//[0, 1, 2, 3]
//
//ababababcababaca
//abacabab
//
//==>
//0'🎯 Algorithm' 카테고리의 다른 글
| [소프티어] 순서대로 방문하기 (1) | 2025.05.14 |
|---|---|
| [리트 코드] Greatest Common Divisor of Strings (0) | 2025.05.13 |
| LIS 이진 검색 활용 (0) | 2025.04.08 |
| 비트 연산 - 집합 (0) | 2025.04.08 |
| [Java] 크루스칼 알고리즘 (0) | 2025.03.27 |