[[TableOfContents]] == ë¬¸ì œ == * [http://183.106.113.109/pool/koi_virus/koi_virus.php?pname=koi_virus] == ê¶Œì˜ê¸° == === 사용 언어 === * C++ === ì•„ì´ë””ì–´ === * [http://183.106.113.109/30stair/KMP_doc/KMP_doc.php?pname=KMP_doc KMP Algorithm] * KMP Algorithmì€ ë¬¸ìžì—´ 검색 ì•Œê³ ë¦¬ì¦˜ì´ë‹¤. 문ìžì—´ì˜ 길ì´ê°€ s, ê²€ìƒ‰í•˜ë ¤ëŠ” íŒ¨í„´ì˜ ê¸¸ì´ê°€ pì¼ë•Œ, 시간복잡ë„ê°€ O(s + p)ë°–ì— ì•ˆ 나오는 ì—„ì² ì¢‹ì€ ì•Œê³ ë¦¬ì¦˜ìž„. Brute-Force로 ì°¾ì„ ë•Œ, O(sp)ê°€ 나오는 ê²ƒì„ ê³ ë ¤í•´ë³´ë©´ ì—„ì²ë‚˜ê²Œ ë¹ ë¦„. * Virusë¼ë©´, ëª¨ë“ ëª¨ë“ í”„ë¡œê·¸ëž¨ì— ì¡´ìž¬í• ê²ƒì´ë‹¤. Virusê°€ 아니ë¼ë©´ ì ì–´ë„ í•œ 프로그램ì—는 존재하지 ì•Šì„ ê²ƒì´ë‹¤. * 한 Programì—서 ê¸¸ì´ kì˜ sub-Patternì„ ì „ë¶€ 구해놓는다. ì´ ê²ƒë“¤ì€ virusì˜ í›„ë³´ê°€ ëœë‹¤. * ê° íŒ¨í„´(후보 ì•ˆì— ìžˆëŠ”)ì„ KMP Algorithmì„ í†µí•´ì„œ ëª¨ë“ í”„ë¡œê·¸ëž¨ì— ê²€ìƒ‰í•´ë³´ë©´ ëœë‹¤. 검색해서 존재하지 않으면, 프로그램ì—서 ì œì™¸í•œë‹¤. * ì´ëŸ° ì‹ìœ¼ë¡œ ëª¨ë“ í”„ë¡œê·¸ëž¨ì„ ê²€ìƒ‰í–ˆì„ ë•Œ, í›„ë³´ì— ì†í•œ íŒ¨í„´ì´ ì•„ë¬´ ê²ƒë„ ì—†ë‹¤ë©´ NO 아니면 YES * 시간 복잡ë„는 O(NM^2) === 풀다가 ê²ªì€ ë¬¸ì œ === * KOI ì§€ì—ë³¸ì„ 5번 ë¬¸ì œì—¬ì„œ ì—„ì² ì«„ì•˜ìŒ. ìœ„ì˜ ì•„ì´ë””어까지 ìƒê°í•˜ëŠ”ë° ì–¼ë§ˆ 걸리지 않았으나, 1ì–µ 5000ë§Œë²ˆì˜ ì—°ì‚° 규모와 ìµœì•…ì˜ ê²½ìš° ëª¨ë“ í”„ë¡œê·¸ëž¨ì´ ê°™ì€ í”„ë¡œê·¸ëž¨ì¼ ê²½ìš°ê°€ 나오면 시간초과가 나올지 모른다는 ê±±ì •ì— ì˜í•´ì„œ 좀 ë” ì‹œê°„ì„ ì¤„ì¼ ìˆ˜ 있는 ë°©ë²•ì„ ê³ ë¯¼í•´ë´„. * í”„ë¡œê·¸ëž¨ì„ í•©ì„ ì´ìš©í•´ì„œ 압축하는 방법. ê¸¸ì´ Kì˜ Sub-Patternì„ O(1)ë§Œì— ê²€ìƒ‰í• ìˆ˜ 있게 í•©ì„ ì´ìš©í•´ì„œ 압축함. * ë¬¸ì œì ì€ Patternì´ ë‹¬ë¼ë„ í•©ì´ ê°™ì„ ìˆ˜ ìžˆìŒ : ë”°ë¼ì„œ ì œê³±í•©ìœ¼ë¡œ 압축하기로 함. * ì œê³±í•© ë˜í•œ 숫ìžëŠ” 같으나 순서만 다른 경우를 파악하지 못하므로, (í•©, Pattern)ì˜ tuple 단위로 ì €ìž¥í•˜ê¸°ë¡œ 함. * 1ì°¨ì 으로 합으로 ê²€ìƒ‰í•˜ê³ , 같으면 tuple까지 검색하ìž. * 처ìŒì—는 Python으로 구현하였ìŒ. ê·¼ë° ìžê¾¸ 시간 초과 나옴. 그러나 ë°ì´í„° 규모를 ìƒê°í•˜ë©´ 시간초과가 나올만한 규모는 아님. 언어ì íŠ¹ì„±ì„ íŒŒì•…í•˜ì§€ 못해서 ìƒê¸´ 결과물로 예ìƒí•˜ê³ 있ìŒ. 한 ì‹œê°„ì€ ë‚ ë¦°ë“¯ :( * ê°™ì€ ì•„ì´ë””어로 C++로 구현하니까 시간 ì•ˆì— ìž˜ 나옴. ã… ã… * Python으로 구현한 누군가는 5ì´ˆì•ˆì— ë‚˜ì˜¤ëŠ”ë° ì–´ë–»ê²Œ 풀었는지 ê¶ê¸ˆí•¨. === 코드 === {{{ #include<iostream> #include<memory.h> using namespace std; int n, k; int pi[1020]; int program[120][1020]; int program_size[120]; int virus_candidate[2020][1020]; bool answer = true; bool virus_check[2020]; int find_pi(int p){ int i = 0, j = -1; pi[0] = -1; while(i < k){ if(j == -1 || virus_candidate[p][i] == virus_candidate[p][j]){ i++; j++; pi[i] = j; } else{ j = pi[j]; } } return 0; } bool kmp(int s, int p){ int i = 0, j = -1; memset(pi, 0, sizeof(int) * 1020); find_pi(p); while(i < program_size[s]){ if(j == -1 || program[s][i] == virus_candidate[p][j]){ i++; j++; } else{ j = pi[j]; } if(j == k){ return true; j = pi[j]; } } return false; } int main(void) { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); cin>>n>>k; for(int i = 0; i<n; i++){ cin>>program_size[i]; for(int j = 0; j<program_size[i]; j++){ cin>>program[i][j]; } } int count = 0; for(int i = 0; i<program_size[0] - k + 2; i++){ for(int j = 0; j<k; j++){ virus_candidate[count][j] = program[0][i + j]; virus_candidate[count + 1][j] = program[0][i + k - j - 1]; } count += 2; } int m = count; for(int i = 1; i<n; i++){ for(int j = 0; j<m; j+=2){ if(!virus_check[j] && !kmp(i, j) && !kmp(i, j + 1)){ virus_check[j] = virus_check[j+1] = true; count -= 2; } } if(count == 0){ answer = false; break; } } if(answer)cout<<"YES"; else cout<<"NO"; } }}}