Algorithm/문자열 (3) 썸네일형 리스트형 String Matching (2) - KMP 알고리즘 KMP algorithm navie string matcher를 다시 생각해보면, 위의 사진 같이 앞에 5개의 문자는 일치하지만 마지막 6번째 문자가 달라서 같지 않다고 나오는 경우, 앞에 5개의 문자는 일치한다는 정보를 버리고 한칸을 shift하고 처음부터 다시 비교하게 된다. KMP알고리즘은 앞에 5개는 일치한다라는 정보를 저장하여 더욱 효율적으로 검색한다는 메인 아이디어로 시작한다. 설계 패턴 자체를 비교하여 필요한 정보를 미리 계산할 수 있습니다. 전체 문자열은 같지 않지만 부분문자열은 같은 경우, 얼마만큼 비교를 skip할 수 있을지 정보를 제공해주는 함수입니다. 위 예시의 경우 ababa까지 일치하였고 앞뒤로 ababa / ababa 3개의 문자가 일치하고 2개의 문자가 일치하지 않으므로 2칸.. String Matching (1) - Navie, Rabin-Karp 알고리즘 String Matching Notation & Terminology T [1 .. n]: n개의 문자의 텍스트 P [1 .. m]: m개의 문자의 패턴 1≤ j ≤m에 대해 T[s+j] = p[j]인 경우 T에서 시프트 s와 함께 P가 발생합니다. P가 T의 시프트 s와 함께 발생하면 s를 유효한 시프트라고 합니다. 그렇지 않으면 잘못된 시프트입니다. Navie algorithm 패턴을 한칸을 옮기며 텍스트가 끝날 때 까지 비교해 보는 방식 의사코드 Navie-String-Matching (T, P) n > P; int n = T.length(); int m = P.length(); for (int s = 0; s < n-m; s++) { int count = 0; for (int i = 0; i < .. Palindrome (회문) palindrome (회문) 회문 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. Ex) TENET, 기러기, 수박이박수 가장 직관적인 방법은 가장 첫글자와 마지막글자, 두번째 글자와 마지막에서 두번째 글자를 서로 다 비교해 보는 것이다. string s; bool palindrome (string s) { int N = s.length()-1; for (int i = 0; i #a#b#d#c#c#d# 각 자리 사이사이에 같은 문자(#)를 넣어 홀수개의 스트링 길이로 만들어주면 된다. 구현 #include #include #include #.. 이전 1 다음