CS - Roadmap.sh/4. String Search and Manipulations(6)
-
4.6 Rabin-Karp’s algorithm(라빈-카프 알고리즘)
CS - 4. String Search and Manipulations - 4.6. Rabin-Karp's algorithm Rabin-Karp’s algorithm Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length n, it performs in O(n+m) time with O(m) space, where m is the length of the pattern. It is often used in bioinformatics to search for DNA patterns. 라..
2024.02.22 -
4.5 Boyer Moore Algorithm(보이어-무어 알고리즘)
CS - 4. String Search and Manipulations - 4.5. Boyer Moore Algorithm Boyer Moore Algorithm 💡Boyer Moore algorithm is a string searching algorithm that is used to find the index of a substring in a string. It is a very efficient algorithm that is used in many applications. It is used in text editors, compilers, and many other applications. 보이어 무어 알고리즘은 문자열에서 하위 문자열의 인덱스를 찾는 데 사용되는 문자열 검색 알고리즘입니다...
2024.02.21 -
4.4. Knuth Morris Pratt (KMP 알고리즘)
CS - 4. String Search and Manipulations - 4.4. Knuth morris pratt Knuth Morris Pratt 💡Knuth morris pratt is a string searching algorithm that uses a precomputed array to find the substring in a string. This array is known as the prefix function. The prefix function is the longest prefix that is also a suffix of a substring. The prefix function is used to skip the characters that are already matc..
2024.02.20 -
4.3 Brute Force Search(완전 탐색)
4. String Search and Manipulations - 4.3 Brute Force Search Brute Force Search Brute force search is a simple algorithm that checks for a pattern in a string by comparing each character of the string with the first character of the pattern. If the first character matches, it then compares the next character of the string with the next character of the pattern and so on. If all the characters of ..
2024.02.17 -
4.2 Suffix Arrays(접미사 배열)
Suffix Arrays Suffix arrays are a data structure that allows us to quickly find all the suffixes of a string in lexicographical order. This is useful for many problems, such as finding the longest common substring between two strings, or finding the number of distinct substrings of a string. 접미사 배열은 사전적 순서로 문자열의 모든 접미사를 빠르게 찾을 수 있는 데이터 구조입니다. 이는 두 문자열 사이의 가장 긴 공통 부분 문자열을 찾거나 문자열의 고유한 부분 문자열의 수를 ..
2024.02.15 -
4. String Search and Manipulations - 4.1 Search Pattern in Text(문자열 검색 및 조작) (텍스트 패턴 검색)
4 String Search and Manipulations - 4.1 Search Pattern in Text String Search and Manipulations (문자열 검색 및 조작) String search and manipulation is a very important topic in computer science. It is used in many different applications, such as searching or replacing a specific pattern, word or character in a string. 문자열 검색과 조작은 컴퓨터 과학에서 매우 중요한 주제입니다. 문자열에서 특정 패턴, 단어 또는 문자를 검색하거나 바꾸는 등 다양한 애플리케이션에서 사용됩..
2024.02.14