본문 바로가기

분류 전체보기

 (115)
문자열의 Suffix Array와 LCP 연산 알고리즘 http://deque.tistory.com/82 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; const int MAX = 1000000; int sa[MAX], temp[MAX], pos[MAX], N, delta, lcp[MAX]; char S[MAX]; //pos[x] : S[x:-1]의 그룹 번호 //sa[x] : suffix들을 정렬했을때, x번째 suffix의 index //temp[x] : suffix들을 정렬했을때, x번째 suffix의 그룹번호 //delta : delta*2의 자릿수만 비교할 것이다 bool cmp(int i, int j) { //pos[i]와 pos[j]를 delta 자릿..
백준 9248 Suffix Array https://kks227.blog.me/221028710658https://stackoverflow.com/questions/17761704/suffix-array-algorithm 링크와 주석으로 설명을 대체한다#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; const int MAX = 1000000; int sa[MAX], temp[MAX], pos[MAX], N, delta, lcp[MAX]; char S[MAX]; //pos[x] : S[x:-1]의 그룹 번호 //sa[x] : suffix들을 정렬했을때, x번째 suffix의 index //temp[x] : suffix들을 정렬했을때, x번째 suff..
백준 4354 문자열 제곱 KMP알고리즘을 수행하면 계산되는 pi배열 ( 다른말로 실패함수)를 이용한다. 다음과 같은 표를 살펴보자(len은 문자열의 길이를 의미) 문자열 pi[len] abab 2 ababab 4 abcabc 3 aaaa 3 asd 0 pi[len]은 문자열의 접두사 = 접미사인 index +1을 가리킨다.즉, pi[len]은 반복되는 문자열의 길이가 반복될 수 있는 최대 길이를 의미한다.이 말은 다른 말로, len - pi[len]이 문자열에서 반복되는 부분문자열의 최소 길이이다.그런데 만약 len-pi[len]이 len으로 나누어 떨어진다면? len은 위에서 말한 부분문자열로만 이루어져있는 것이다.따라서 위의 예시처럼 text[0~len-pi[len]]만큼의 부분문자열이 반복되는 것을 볼수 있다. 한편, le..
백준 1701 Cubeditor KMP알고리즘을 수행할 때 pi를 구한다.그런데 만약 pattern에 2번 이상 반복되는 부분 문자열이 있다면 pi에 그 부분문자열의 길이가 기록 된다. 예를들어 pattern이 aabcaa라고 하자.그렇다면 index가 6일때 접두사와 접미사가 같은 부분이 나오고, pi[6] = 2로 기록된다.그런데 이 값은 접두사와 접미사가 같은 부분의 길이를 의미하기도 한다. 따라서 pi[6]의 값은 pi[0~6]의 최대 길이 중복 부분 문자열의 길이(우리가 구하고 싶은 값)가 된다. 또 다른 예로 pattern을 aabcaabxx라고 하자.이 패턴에서는 index가 6일때 마찬가지로 접두사와 접미사가 같은 부분이 나오고, index가 7일때 또 한번 나온다. (pi[6] = 2, pi[7] = 3)따라서 pi의 ..
[python3] 백준 1786 찾기 KMP알고리즘으로 풀면 된다. http://deque.tistory.com/78 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0 and text[i] !..
KMP 알고리즘 http://mygumi.tistory.com/61http://bowbowbow.tistory.com/6 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0..
백준 1015 수열 정렬 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include using namespace std; vector sortArr; vector prevArr; vector isFill; int main() { int N; scanf("%d", &N); int temp; for (int i = 0; i < N ; i++) { scanf("%d", &temp); sortArr.push_back(temp); prevArr.push_back(temp); isFill.push_back(false); } sort..
백준 1016 제곱 ㄴㄴ수 에라토스테네스의 체 문제이다 만약, "min에서 max까지 순회하면서 각 값이 2~백만의 값의 제곱수로 나누어 떨어질경우 pass" 하는 식으로 알고리즘을 짜면 n^2이 되기때문에 시간초과가 난다. 따라서 백만짜리 배열을 선언하고 # "i"는 2~max까지 순회하며 다음을 반복 ## (i*i) * j 는 제곱 YES수이므로 배열[(i*i) * j]를 true로 바꾼다. 다만 (i*i) * j의 값을 min~max 사이로 해싱한다 민다 j+=1. ## # 마지막에 배열에서 false가 몇개인지 샌다 # 와 같은 알고리즘은 배열의 값을 중복해서 체크하는 경우가 거의 없기 때문에 시간복잡도를 n으로 봐도 되므로(즉, 백만) 시간 안에 해결 가능하다. #include using namespace std; boo..

티스토리툴바