문제설명입력 & 출력잘못된 풀이1. charAt() 메서드 사용public class BOJ16916 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String S = br.readLine(); String P = br.readLine(); boolean isSubString = false; for (int i = 0; i 2. contains() 메서드 사용public class BOJ16916 { public static void ma..
KMP
개요문자열 검색 알고리즘은 두 문자열을 비교하여 특정 패턴이 주어진 텍스트에서 처음 등장하는 위치를 찾거나, 특정 조건을 만족하는 서브스트링을 효율적으로 찾는 데 사용됩니다. 일반적인 문자열 검색은 O(N * M) 복잡도를 가지며, 이는 텍스트의 길이 N과 패턴의 길이 M에 비례하여 비교를 수행하기 때문에 긴 문자열을 다룰 때 비효율적입니다. 이를 개선하기 위해 KMP(Knuth-Morris-Pratt) 알고리즘이 고안되었습니다. 이번 포스팅에서는 KMP(Knuth-Morris-Pratt) 알고리즘에 대해서 정리하고자 합니다. KMP(Knuth-Morris-Pratt) 알고리즘이란❓KMP 알고리즘의 핵심은 pi 배열을 사용해, 패턴 내에서 중복된 접두사와 접미사 정보를 미리 계산하고 이를 활용하여 텍스..
