Knuth Morris Pratt(KMP)는 왼쪽에서 오른쪽으로 문자를 확인하는 알고리즘입니다. 패턴에 하위 패턴이 두 개 이상 나타날 때 해당 속성을 사용하여 최악의 경우 시간 복잡성을 개선합니다. KMP의 시간 복잡도는 O(n)입니다. 입력 및 출력 Input: Main String: “AAAABAAAAABBBAAAAB”, The pattern “AAAB” Output: Pattern found at location: 1 Pattern found at location: 7 Patter

문자열에서 가장 긴 회문 부분 문자열을 찾기 위해 Manacher 알고리즘을 사용할 수 있습니다. 각 문자를 선택하여 왼쪽 및 오른쪽 포인터를 사용하여 회문이 있는지 찾습니다. 정보를 저장하는 또 다른 배열이 있습니다. 이 정보에서 회문의 길이를 쉽게 찾을 수 있습니다. 각 문자에 대해 배열에 정보가 저장됩니다. 전체 문자열을 탐색한 후 생성된 배열에서 가장 긴 회문 부분 수열을 찾을 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)입니다. 입력 및 출력 Input: String: “levelup” Outp

순진한 패턴 검색은 다른 패턴 검색 알고리즘 중에서 가장 간단한 방법입니다. 패턴에 대한 기본 문자열의 모든 문자를 확인합니다. 이 알고리즘은 작은 텍스트에 유용합니다. 전처리 단계가 필요하지 않습니다. 문자열을 한 번 확인하여 하위 문자열을 찾을 수 있습니다. 또한 작업을 수행하기 위해 추가 공간을 차지하지 않습니다. Naive Pattern Search 방법의 시간 복잡도는 O(m*n)입니다. m은 패턴의 크기이고 n은 주 문자열의 크기입니다. 입력 및 출력 Input: Main String: “ABAAABCDBBA

Rabin-Karp는 보다 효율적인 방법으로 패턴을 찾기 위한 또 다른 패턴 검색 알고리즘입니다. 또한 창을 하나씩 이동하여 패턴을 확인하지만 모든 경우에 대해 모든 문자를 확인하지 않고 해시 값을 찾습니다. 해시 값이 일치하면 각 문자만 확인하려고 합니다. 이 절차는 알고리즘을 보다 효율적으로 만듭니다. 시간 복잡도는 O(m+n)이지만 최악의 경우 O(mn)입니다. 입력 및 출력 Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC” O

주어진 문자열에서 가능한 모든 접미사를 얻을 수 있습니다. 접미사를 사전순으로 정렬한 후 접미사 배열을 얻을 수 있습니다. 접미사 배열은 접미사 트리를 사용하여 구성할 수도 있습니다. 접미사 트리의 DFS 탐색을 사용하여 접미사 배열을 얻을 수 있습니다. 접미사 배열은 선형 시간에서 접미사를 찾는 데 도움이 됩니다. 이진 검색 유형 절차를 사용하여 접미사 배열을 사용하여 부분 문자열을 찾을 수도 있습니다. 시간 복잡도는 O(m log n) 입력 및 출력 Input: Main String: “BANANA”, P

텍스트에서 모든 접미사를 생성하여 트리 구조를 만들 수 있습니다. 우리는 텍스트에 있는 모든 패턴이 텍스트에서 가능한 접미사 중 하나의 접두사여야 한다는 것을 알고 있습니다. 모든 접미사의 Trie를 구축하여 선형 시간에 모든 하위 문자열을 찾을 수 있습니다. 모든 접미사는 문자열 종료 기호로 끝납니다. 각 노드에서 경로가 있으면 앞으로 이동하고, 그렇지 않으면 패턴을 찾을 수 없음을 반환합니다. 이 알고리즘의 경우 시간 복잡도는 O(m+k)이며, 여기서 m은 문자열의 길이이고 k는 텍스트의 패턴 빈도입니다. 입력 및 출력 Inp

이 알고리즘에서 Z 배열을 생성해야 하기 때문에 이 알고리즘의 이름은 Z 알고리즘입니다. Z 배열의 크기는 텍스트 크기와 동일합니다. 이 배열은 기본 문자열의 현재 문자부터 시작하여 가능한 가장 긴 부분 문자열의 길이를 저장하는 데 사용됩니다. 처음에는 문양과 본문이 본문과 문양에 없는 특수한 기호로 연결되어 있다. P가 패턴이고 T가 본문이면 연결 후 P$T가 됩니다($가 P와 T에 존재하지 않는다고 가정). 이 알고리즘의 경우 시간 복잡도는 m이 패턴의 길이이고 n이 주 문자열의 길이이므로 O(m+n)입니다. 입력 및 출력 I

무방향 그래프에서 Hamiltonian 경로는 각 정점을 정확히 한 번 방문하는 경로이고 Hamiltonian 순환 또는 회로는 마지막 정점에서 간선이 있는 Hamiltonian 경로입니다. 첫 번째 정점으로. 이 문제에서는 그래프에 해밀턴 주기가 포함되어 있는지 여부를 확인하려고 합니다. 그리고 Hamiltonian 주기가 있는 경우 주기도 인쇄하십시오. 입력 및 출력 Input: The adjacency matrix of a graph G(V, E). Output: The algorithm finds the Hamiltoni

연결된 그래프 G(V, E)가 있고 모든 모서리에 대한 가중치 또는 비용이 제공됩니다. Kruskal의 알고리즘은 그래프와 비용을 사용하여 최소 스패닝 트리를 찾습니다. 병합 트리 접근 방식입니다. 처음에는 다른 트리가 있는데 이 알고리즘은 비용이 최소인 가장자리를 취하여 병합하여 단일 트리를 형성합니다. 이 알고리즘의 시간 복잡도는 O(E log E) 또는 O(E log V)이며, 여기서 E는 에지의 개수이고 V는 정점의 개수입니다. 입력 및 출력 Input: Adjacency matrix Output: Edge: B-

C(c1, c2, …Cn) 코인 목록이 있으며 V 값도 제공됩니다. 이제 문제는 최소한의 코인을 사용하여 기회를 V로 만드는 것입니다. 참고 - 무한한 수의 동전이 있다고 가정합니다. C 이 문제에서는 서로 다른 동전 집합 C{1, 2, 5, 10}가 주어졌을 때 각 유형의 동전 수가 무한대라고 생각합니다. 요청된 값을 변경하기 위해 모든 유형의 최소 동전 수를 사용하려고 합니다. 예를 들어 값이 22인 경우 최소값으로 {10, 10, 2}, 3개의 동전을 선택합니다. 이 알고리즘의 시간 복잡도 id O(V), 여기서 V는

도착 및 출발 시간 목록이 제공됩니다. 이제 문제는 기차가 기다리지 않기 때문에 철도에 필요한 최소 플랫폼 수를 찾는 것입니다. 모든 타이밍을 정렬된 순서로 정렬하면 솔루션을 쉽게 찾을 수 있습니다. 기차가 도착했지만 역을 떠나지 않았을 때 추적하기가 쉬울 것입니다. 이 문제의 시간 복잡도는 O(n Log n)입니다. 입력 및 출력 Input: Lists of arrival time and departure time. Arrival: {900, 940, 950, 1100, 1500, 1800} Departure: {910, 12

연결된 그래프 G(V, E)가 있고 모든 모서리에 대한 가중치 또는 비용이 제공됩니다. Prim의 알고리즘은 그래프 G에서 최소 스패닝 트리를 찾습니다. 그것은 성장하는 나무 접근 방식입니다. 이 알고리즘은 트리를 시작하기 위해 시드 값이 필요합니다. 시드 정점이 성장하여 전체 트리를 형성합니다. 문제는 두 세트를 사용하여 해결됩니다. 한 세트는 이미 선택된 노드를 보유하고 다른 세트는 아직 고려되지 않은 항목을 보유합니다. seed vertex에서 최소 edge cost를 기준으로 인접한 vertex를 취하므로 노드를 하

이전 알고리즘과 유사합니다. 여기서 유일한 차이점은 그래프 G(V, E)가 인접 목록으로 표시된다는 것입니다. 시간 복잡도 인접 목록 표현은 O(E log V)입니다. 입력 및 출력 Input: The cost matrix: Output: Edge: A--B And Cost: 1 Edge: B--E And Cost: 2 Edge: A--C And Cost: 3 Edge: A--D And Cost: 4 Edge: E--F And Cost: 2 Edge: F--G And Cost: 3 Total Cost: 15 알고리즘 prims(

항목 목록이 제공되며 각 항목에는 고유한 가치와 무게가 있습니다. 아이템은 최대 무게 제한이 W인 배낭에 넣을 수 있습니다. 문제는 W보다 작거나 같은 무게를 찾아 값을 최대화하는 것입니다. 배낭 문제에는 두 가지 유형이 있습니다. 0 – 1 배낭 프랙셔널 배낭 0 – 1 배낭의 경우 항목을 더 작은 조각으로 나눌 수 없으며, 분수 배낭의 경우 항목을 더 작은 조각으로 나눌 수 있습니다. 여기서 우리는 분수 배낭 문제에 대해 논의할 것입니다. 이 알고리즘의 시간 복잡도는 O(n Log n)입니다. 입력 및 출력 입력:최대

이 알고리즘은 주어진 모든 키워드 세트의 모든 항목을 찾는 데 유용합니다. 일종의 사전 매칭 알고리즘입니다. 모든 키워드를 사용하는 트리 구조를 사용합니다. 트리를 만든 후에는 트리를 자동으로 변환하여 선형 시간으로 검색을 시도합니다. Aho-Corasick 알고리즘에는 세 가지 단계가 있습니다. 이동, 실패 및 출력 . 이동 단계에서는 모든 키워드를 사용하여 트리를 만듭니다. 다음 단계 또는 실패 단계에서 일부 키워드의 적절한 접미사를 얻기 위해 역전이를 찾으려고 시도합니다. 출력 단계에서 자동 장치의 모든 상태 s에 대해 상

애너그램은 기본적으로 주어진 문자열이나 패턴의 모든 순열입니다. 이 패턴 검색 알고리즘은 약간 다릅니다. 이 경우 정확한 패턴만 검색되는 것이 아니라, 텍스트에서 주어진 패턴의 가능한 모든 배열을 검색합니다. 이 문제를 해결하기 위해 전체 텍스트를 패턴과 같은 길이의 여러 창으로 나눕니다. 그런 다음 패턴의 각 문자를 카운트하여 배열에 저장합니다. 또한 각 창에 대해 count 배열을 찾은 다음 일치 여부를 확인하려고 합니다. 아나그램 패턴 탐색 알고리즘의 시간 복잡도는 O(n)입니다. 입력 및 출력 Input: The main

나쁜 문자 발견적 방법은 Boyer Moore 알고리즘의 접근 방식 중 하나입니다. 또 다른 접근 방식은 Good Suffix 휴리스틱입니다. 이 방법에서 우리는 패턴과 일치하지 않는 주 문자열의 문자를 의미하는 잘못된 문자를 찾으려고 노력할 것입니다. 불일치가 발생하면 불일치가 일치할 때까지 전체 패턴을 이동합니다. 그렇지 않으면 패턴이 잘못된 문자를 지나 이동합니다. 여기서 시간 복잡도는 최상의 경우 O(m/n)이고 최악의 경우 O(mn)입니다. 여기서 n은 텍스트 길이이고 m은 패턴 길이입니다. 입력 및 출력 Input: Ma

보이어 무어 알고리즘의 또 다른 접근 방식입니다. 때로는 Good Suffix 휴리스틱 방법이라고 합니다. 이 경우 전처리 테이블이 접미사 테이블로 생성됩니다. 이 절차에서는 패턴의 마지막 문자에서 부분 문자열 또는 패턴을 검색합니다. 주 문자열의 하위 문자열이 패턴의 하위 문자열과 일치하면 일치하는 하위 문자열의 다른 항목을 찾기 위해 이동합니다. 메인 문자열의 접미사인 패턴의 접두사를 찾기 위해 이동할 수도 있습니다. 그렇지 않으면 패턴의 전체 길이를 이동합니다. 입력 및 출력 Input: Main String: “A

퀵소트 기술은 목록을 두 부분으로 분리하여 수행됩니다. 처음에는 분할 알고리즘에 의해 피벗 요소가 선택됩니다. 피벗의 왼쪽 부분은 피벗보다 작은 값을 보유하고 오른쪽 부분은 더 큰 값을 보유합니다. 분할 후 동일한 절차를 사용하여 각각의 개별 목록이 분할됩니다. 퀵소트 기법의 복잡성 시간 복잡도:최상의 경우와 평균적인 경우는 O(n log n), 최악의 경우는 O(n^2)입니다. 공간 복잡도:O(log n) 입력 및 출력 Input: The unsorted list: 90 45 22 11 22 50 Output: Array be

기수 정렬은 비비교 정렬 알고리즘입니다. 이 정렬 알고리즘은 동일한 위치와 값을 공유하는 숫자를 그룹화하여 정수 키에서 작동합니다. 기수는 숫자 체계의 기초입니다. 십진법에서 기수 또는 기수는 10이라는 것을 알고 있습니다. 따라서 일부 십진법을 정렬하려면 숫자를 저장할 10개의 위치 상자가 필요합니다. 기수 정렬 기법의 복잡성 시간 복잡도:O(nk) 공간 복잡성:O(n+k) 입력 및 출력 알고리즘 radixSort(배열, 크기, maxDigit) 입력 - 데이터 배열 및 배열의 ​​총 개수, 최대 개수의 자릿수 출력 -