본문 바로가기

알고리즘/메모44

라빈 카프, 문자열 해싱 어떤 문자열의 부분 문자열을 해싱하려 할때, map을 이용하여 mp[s.substr(i,k)]꼴로 해시를 사용하기엔 이미 substr이 선형시간을 잡아먹으므로 바람직하지 않다. 문자열 s에 대해 해시함수를 다음과 같이 쓰는 걸 라빈카프라 한다. (혼동을피하기위해 a->p p->MOD) 큰 소수 MOD의 원시근으로 p를 고르는 것이 유리하다. 문자열 s의 i번째부터 시작하는 길이k인 부분문자열을 위 식에 넣어 정리해보면 다음과 같이 점화식이 나온다. H[i+1] = p*H[i] - (p^k)*s[i] + s[i+k] for (int i = 1; i 2020. 3. 21.
마나커 (팰린드롬) 길이가 홀수인 문자열 s에 대해 다음을 O(n)에 구할 수 있다. 길이가 짝수인 문자열은 중간에 더미문자를 추가해준다. dp[i] : s[i]를 중심으로 하는 가장 긴 팰린드롬의 반지름 (예를들어, s : aba -> dp : 0 1 0) n = s.size() i : [0~n-1] 순서대로 초기화 할 것. 0~i-1까지 팰린드롬 중 가장 우측의 오른쪽 경계 r과 그때의 인덱스 k을 이용해서 dp[i]초기화 다음과같이 경우를 나누어 초기화해 준다. 1) i p= 2*k-i) 1-1) p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬에 속하는 경우 dp[i] = dp[p] 1-2) p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬의 왼쪽으로 경계를 넘는.. 2020. 3. 20.
조합의 소수 모듈러 값 빠르게 구하기 (n C m % p) https://ryulstory.tistory.com/62 페르마 소정리에 따르면 p가 소수인 경우 a^(p-1) = 1 (mod p) 1/a mod p == a^(p-2) 즉 다음을 만족함 (a*b) % p = (a%p) * (b%p) (a/b) % p = (a%p) * (b^(p-2) % p) nCk (mod p) = n! /(k! * (n-k)!) (mod p) = (n! mod p) * ((k! * (n-k)!)^(p-2) mod p ) 다음 두 배열을 전처리해준다. O(n) fac[x] : x! % MOD fac_inv[x] : (x!)^(-1) %MOD -> n * inverse(n!) = inverse((n-1)!) 를 이욯 O(1)에 nCm % p 를 구할 수 있다. const ll MOD.. 2020. 3. 10.
구간 만들기 자주나오니까 복붙하지말고 따라서 타이핑 0또는 1로 이뤄진 불린타입 배열 a에서 1 구간을 vector a에 {시작점, 끝점} 끝점으로 넣는 코드 int lo = -1, hi = -1; for (int i = 0; i 0 && a[i - 1] == 0)) lo = hi = i; else hi++; if (i == n - 1) ap.push_back({ lo,hi }); } else if (a[i - 1] == 1) ap.push_back({ lo,hi }); } 2020. 3. 9.

티스토리툴바