반응형 Pattern2 [자료구조] KMP(Knuth-Morris-Pratt) Algorithm KMP 알고리즘은 문자열 내에서 특정 패턴을 엄청나게 빠르게 찾아주는 알고리즘입니다. 해당 패턴의 위치를 빠르게 알 수 있지요. KMP알고리즘은 이전 포스팅의 마지막에 다루었던 패턴을 찾는 방법처럼 스트링과 패턴의 불일치가 발생했을 때 최대한 중복된 연산을 피하면서 문자열과 비교할 수 있도록 합니다. 이렇게 하기 위해서는 먼저 얼마나 중복연산을 피할것인지 판단하기 위한 값들이 필요합니다. 이를 failture function이라고 한다. failure function은 패턴문자열의 접두사와 접미사의 일치하는 부분을 계산하고 이를 fail 배열에 저장합니다. fail 배열의 첫 번째 인덱스의 값은 -1로 설정합니다. 인덱스의 의미는 현재 패턴의 문자가 패턴의 첫문자부터 #번째 문자까지 일치한다는 것을 말합.. 2024. 4. 14. [자료구조] 문자열(Strings) 문자열이란 한정된 순서를 가진 크기가 0이상인 문자들의 집합을 말합니다. C에서는 배열을 통해서 문자열을 나타낼 수 있습니다. #define MAX_SIZE 100 char s[MAX_SIZE] = "dog"; char t[MAX_SIZE] = "house"; 또한 선언할 때에는 다음과 같이 선언할 수도 있습니다. char s[] = "dog"; char t[] = "house"; 이때에는 문자의 개수+1개 만큼 크기가 자동으로 할당 됩니다. 하지만 다음과 같이 선언할 수 없습니다. char u[]; //compile error 배열을 초기화하지도 않고, 크기도 정해주지 않는다면 컴파일 에러가 발생합니다. 이번에는 strcat 함수를 이용하여 문자열에 대해 더 알아보겠습니다. #include #inclu.. 2024. 4. 14. 이전 1 다음 반응형
