구사과

(Stankonia, 2000)

https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명 아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다. * 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도..

문자열 S와 T가 주어졌을 때, S의 부분 문자열 중 T가 몇번 등장하는 지를 찾는 문제를 생각해보자. 예를 들어 "koosaga" 에서 "saga" 를 찾으면 "koos" != "saga", "oosa" != "saga", "osag" != "saga", "saga" == "saga" 여서 총 한번 등장하고, "aa" 를 찾으면 "ko" != "aa", "oo" != "aa", "os" != "aa", "sa" != "aa", "ag" != "aa", "ga" != "aa" 여서 단 한번도 등장하지 않는다. N = (S의 길이), M = (T의 길이) 라 하자. S[i, j] = (i번째 문자에서 j-1번째 문자까지를 포함하는 부분 문자열) 이라고 하자. 예를 들어 "koosaga"[0, 3] = "k..

http://agc013.contest.atcoder.jp/ A. Sorted Arrays단순 구현인데 코딩이 의외로 쉽지 않았다. B. Hamiltonish Path신기한 문제. path 어디에나 붙여도 되는 줄 알고 진짜 해밀턴 경로 문젠줄 알아서 좀 해멨다. 그런 경로를 아무거나 찾으면 되는 것이니 path 끝에 붙일 수 있는 정점이 있다면 무조건 붙여보는 식으로 풀면 된다. dfs로 쉽게 구현 가능. C. Ants on a Circle부딪힐 때 서로 방향을 바꾼다고 생각하지 않고, 서로의 번호만 바꿔서 가던 길 그대로 간다고 생각하면 복잡하지 않다. 이건 워낙 유명한 유형이니까 뭐...그렇게 하면 전체 개미의 위치는 아주 쉽게 알 수 있다. 하지만 무슨 개미가 어떤 위치에 있는지는 어떻게 알까. ..

H번 문제의 풀이를 "조속한 시간" 내에 올리겠다고 공식 홈페이지에 올라왔지만, 사실 모두의 기억 속에서 잊혀져 버린 문제이다. 그래서 아무도 작업하고 있지 않았다..얼마 전에 BOJ 즐겨찾기를 보다가 기억이 나서 풀이를 작성했다. 풀이 tex 파일과 함께 첨부한다.

시험이 끝나면 블로그 주소를 koosaga.myungwoo.kr에서 koosaga.com 으로 바꿀 예정입니다. 내부 링크 같은 것도 다 조정을 해야 해서 아마 다음주 중에 시간이 남으면 하지 않을까 싶어요...지금도 koosaga.com으로 들어오면 리다이렉션이 됩니다. 그러니까 북마크 같은 거는 일찍 바꾸셔도 괜찮습니다. + 4/24 00:40내부 링크 조정을 했습니다. 곧 반영될 예정인데, 그 전까지는 접속에 불편함이 있을 수 있습니다. 제가 실수한게 있다면 알려주세요.그리고 글 접근 기본 옵션을 번호로 줬습니다. SEO 때문에 원래 이름으로 한 것이었는데 귀찮기만 해서 그냥...

A. CNF-SAT 몰라 B. Almost pattern matching 몰라 C. Two paths http://codeforces.com/blog/entry/51228?#comment-351103 D. Mushrooms after rain strikes back몰라 E. Epic Battle alex9801 선배가 풀었다. 필요충분조건이 한정적이라 간단한 케이스 판별로 풀 수 있다고 함 F. Reachability 편의상 어떤 점들도 degree가 0이지 않다고 생각한다면, 각각의 starting point가 도달할 수 있는 정점의 개수가 구간의 형태로 나온다. starting point를 증가시키면서 가능한 다음 구간들을 모두 시도해 보면 (다음 구간은, S_i

[2017.01.25 : 처음 작성][2017.03.03 : las / pod 문제 번역 실수가 있었습니다. 죄송합니다..][2017.03.13 : klo 문제 번역 실수가 있었습니다. 죄송합니다.. 이 글은 이제 마감합니다.]https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2016/Problems폴란드어 문제만 번역합니다. Day1 ~ Day4는 영어로 문제가 나오니까 그걸로 읽으시면 됩니다.Day 5Kłódka (klo)0 이상 K 미만의 정수 배열 a[0] ... a[n-1] 이 있다. 0 이상 n-2 이하의 정수 x에 대해, 당신은 다음 두 연산을 할 수 있다. * inc(x) : a[x]와 a[x+1] 에, v

결과본선에 진출했다. 그날 편두통이 있어서 걱정을 많이 했다. 편두통 심하면 아무 것도 못해서... 사실 대회 전에는 졸리고 편두통도 조금 있는거 같아서 거의 본선에 대해 체념 했는데, 다행히도 대회 중에 크게 컨디션 문제가 생기진 않았다. 편두통은 연휴 끝나면 병원 가서 끝을 봐야겠다. 타이레놀도 잘 안들어서 힘들다... 딱히 모난 거 없이 했던 거 같다. A B C중에서 정말 못 풀겠다 싶었던 거는 없었고, 코딩도 그렇게 시간이 오래 걸리지는 않았다. 문제는 뭐 그냥 그냥 괜찮았던 거 같은데, 그래도 얼마 전에 버추얼 돌았던 2016 R3가 훨씬 재밌었다. A. Salient StringsSuffix array가 주어졌을 때 이를 만족하는 string을 복원하는 문제이다. 처음에 잘 모르겠어서 다른 ..

(Mirror Traffic, 2011) 와....