Algorithm/String 검색 결과

해당 글 7건

Suffix Array O(NlgNlgN)과 O(NlgN) 구현 및 설명.

최근 입사 동기가 물어본 일도 있고 해서 정리를 해봤다. 먼저 어떤 스트링(문자열)의 Suffix Array를 구한다는 것이 무슨 뜻인지부터 살펴보자.결론부터 얘기하자면, mississipi란 스트링이 주어졌을 때 Suffix Array라는 것을 구하면 9741086352가 되겠다. 이제 조금씩 살펴보자.어떤 string의 suffix라는 것은 접미사를 의미한다.mississipi란 string에는 [0] mississipi[1] ississipi[2] ssissipi[3] sissipi[4] issipi[5] ssipi[6] sipi[7] ipi[8] pi[9] i 이렇게 위와 같이 10가지 suffix가 있을 것이다.해당..
Algorithm/String 2017. 6. 11. 22:05

Rabin-Karp Fingerprinting 이란?

Rabin-Karp Fingerprinting이란?긴 String을 Hashing해서 사용할 때 쓰는 알고리즘이다. k길이의 스트링 str[i, i+k-1]을 들여다 보면 k만큼의 시간이 걸린다.그리고 나서 i+1부터 다시 k길이의 스트링을 들여다 보면 또 k만큼의 시간이 걸린다. 그럼 어떻게 할까?hash를 재미있게 이용하면 된다. hashing하는 function을 f()라고 하면 그니까 hashmap을 만들때 처음 k길이의 스트링에 대한 hash값을 만든다면 인덱스를 하나 옮긴 스트링의 hash를 에 구할 수 있다. 여기서 x값은 스트링 s에 들어오는 문자의 종류에 따라 설정하면 된다. 영어의 대소문자만 쓴다면 26+26 = 52개로 지정할 수도 있고, 아스키코드에 해당하는 문자열이 다 들어오는 경..
Algorithm/String 2017. 1. 5. 18:39

Suffix Array & LCP (C++11 Code Only)

여기엔 코드만 올린다. 설명은 바로 이전 글 2개에 걸쳐서 설명이 되어있다. 내가 acm reference로 썼던 나름 깔끔한 코드다. 지금 코드는 어떨지 모르겠는데 koosaga님 블로그를 통해 배웠기 때문에 상당부분 koosaga님 코드와 비슷할 거라 생각한다. 그래서 출처는 koosaga님 블로그로 밝힌다. (http://koosaga.myungwoo.kr/entry/Suffix-Array-접미사-배열) 다만, 코드는 내가 직접 작성하긴 했다. Suffix Array: → 설명이 있는 내가 올린 포스팅: http://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN과-ONlogN-구현-및-설명 (2017.06.11 수정) LCP: → 약간 설명이 있는 내가 올린 ..
Algorithm/String 2016. 11. 20. 02:55

문자열 처리 알고리즘 - LCP

LCP (Longest Common Prefix) 문자열이 하나만 주어졌을때 공통된 문자열(substring; subsequence가 아님)의 최대 길이가 얼마인지 구해야 하는 문제가 주어졌다고 하자. 이 때 이 문자열에 대한 Suffix Array를 구해놨다면 O(N)에 문제에 대한 답을 구할 수 있다. 그럼 이 부분을 KMP로 구할 수 있을까? 안된다. Needle에 대한 스트링이 O(N^2)개 만큼 존재하는데, 이걸 모두 비교하려면 O(N^3)이 걸릴 것이다. 그래서 나온 방법이 SA를 구한 상태에서 LCP를 O(N)에 구하는 방법이다. (이전에 내가 올린 포스팅에서 Suffix Array를 O(NlogN)에 구할 수 있는 방법만 소개하였으나 O(N)에 구할 수도 있다. 그러면 SA구하고 LCP까지..
Algorithm/String 2016. 11. 20. 02:48

문자열 처리 알고리즘 - Suffix Array

해당 posting은 다시 작성되었습니다. 새글 보러 가기: http://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN과-ONlogN-구현-및-설명 Suffix Array (접미사 배열) 만약 suffix array에서 1,2,4,8 이런식으로 건너뛰면서 소팅하는 것 자체가 이해가 안됐다면, https://algospot.com/forum/read/2779/#c12715 여기 갓 설명글이 있다. 이 글 읽으면 무조건 이해가 될 것이다. 나도 여기서 막혔었고, 종만북 보면 이 문자열 파트 부분 설명이 상당히 좋지 않기 때문에 대부분 여기서 헤맨다.
Algorithm/String 2016. 11. 20. 02:31

문자열 처리 알고리즘 - KMP

문자열 처리 알고리즘 나름 블로그의 모양새를 갖추기 위해 오늘부터 문자열처리 알고리즘에 대해 작성해보려고 한다. ㅋㅋ 1. KMP Algorithm 어떤 문자열(H)에서 내가 찾고자 하는 문자열(N)이 있는지 확인하려면 어떻게 해야할까? H와 N을 하나하나씩 비교하다가 match되지 않는 부분이 나오면 N 문자열을 통째로 한칸 이동해서 다시 처음부터 비교하면 될 것이다. 그럼 시간복잡도는 … ㄷㄷㄷ H와 N이 10만씩 주어지면 100억이나 된다. Tip: H는 Hay의 약자, N은 Needle의 약자이다. 건초더미에서 바늘찾는다고 생각하면 된다. ㅋ 그럼 어떻게 할까? 이 문제를 만에 해결하는 방법이 있으니 그게 바로 KMP 알고리즘이다. 근데 이게 처음 코드만 보면 사실 뭐하는건지도 모르겠고, 설명들어..
Algorithm/String 2016. 11. 20. 02:00

최대공약수 (GCD: Greatest Common Divisor)

123456789#include using namespace std;long long gcd(long long b, long long s) { return s?gcd(s,b%s):b; }int main() { long long x,y; scanf("%lld%lld",&x,&y); printf("%lld",gcd(x,y)); return 0;}Colored by Color Scriptercs 처음 ps를 배울 때 gcd구하는 법도 몰랐다. 뭔가 이런 코드를 보고 엄청 감동받았던 적이 있었는데 ㅋㅋ 지금 생각해보면 참 안타까운 시절이었다. 설명은 없다. 어차피 자세한 설명은 구글에 널렸다. ㅋ 가서 찾아보시길...
Algorithm/String 2016. 11. 19. 17:24