본문 바로가기

알고리즘225

라빈 카프, 문자열 해싱 어떤 문자열의 부분 문자열을 해싱하려 할때, 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.
global round #7 D2 - Prefix-Suffix Palindrome (실패함수, prefix function) https://codeforces.com/contest/1326/problem/D2 문자열 s가 주어질 때, s의 prefix a, suffix b를 이어붙여 만들 수 있는 최대길이 팰린드롬을 출력하라. (단, a+b 0 && t[i] != t[j]) j = pref[j - 1]; if (t[i] == t[j]) pref[i] = ++j; } int tt; string inp; string prefixPalin(string a) { string b = a; reverse(b.begin(), b.end()); string s = a + "#" + b;//더미문자 추가해서 s길이 홀수로 강제 vector pref(s.size()); int j = 0; for (int i = 1; i < s.size(); i.. 2020. 3. 20.
BOJ 11813 - GALAKSIJA (disjoint set, tree, 오프라인쿼리) https://www.acmicpc.net/problem/11813 http://blog.naver.com/nywoo19/221436385751 위 블로그 참고했습니다. 가중치있는 트리가 주어진다. 간선을 주어진 순서대로 자를 것. 자르고 난 후 원하는 값을 그때 그때 출력하는 문제. 원하는 값: 전체 경로에서 경로에포함된 모든 간선의 가중치의 xor값이 0인 경우의 수 트리를 자른다 -> 거꾸로 간선을 이어붙이는 편이 훨씬 쉽다. 1. a ^ b == 0 a == b 2. xor(u,v) : xor(1,u) ^ xor(1,v)임을 이용해야 한다. map mp[MAX]에서 mp[u] = {x, cnt} : 대표값이 u인 set에 포함된 v 중 xor(1,v)값이 x인 것의 개수 cnt 간선 (u,v)를 .. 2020. 3. 18.

티스토리툴바