목록문자열매칭 (2)

코딩뚠뚠

[기본문제풀이] rabin karp 알고리즘

풀이 일시 : 2020-08-22 ​ 라빈카프 알고리즘 : 문자열 매칭 알고리즘으로 해시기법을 이용한다. 충돌하는 경우에는 포인터를 이용해 연결자료구조(link)를 이용해 해결한다. ​ 문제 : 라빈카프 알고리즘을 이용하여 "ababacabacaabacaaba" 에서 "abacaaba"의 시작점을 찾아라 ​ 풀이 : #include #include using namespace std; void hashs(string parent, string pattern) { int parentHash=0, patternHash=0, power = 1; int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i
알고리즘 문제풀이/기본문제풀이 2020. 12. 28. 00:59
[기본문제풀이] KMP알고리즘

풀이 일시 : 2020-08-21 ​ KMP알고리즘 : Knuth Morris Pratt 알고리즘 / 대표적인 문자열(string)매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘 ​ 문제1 : 일반 문자열 매칭 알고리즘 (KMP알고리즘 X) ​ 풀이 : BCDEF가 있고 그 중 DE를 찾을거면 자리를 하나씩 옮기며 비교하면서 매칭한다. O(N*M) #include using namespace std; int findString(string parent, string pattern) { int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i ABCDABEDFS 에서 ABE를 찾고자..
알고리즘 문제풀이/기본문제풀이 2020. 12. 28. 00:58
이전 Prev 1 Next 다음