레야몬

1. 문제 전광판의 크기는 전광판에서 한 번에 보이는 최대 문자수를 나타낸다. 광고업자는 길이가 N인 광고를 무한이 붙여서 광고한다. 세준이가 어느 순간 전광판을 쳐다봤을 때, 그때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오. - 1 - 광고판 크기 \(L(1 \leq L \leq 1,000,000)\) - 2 - 현재 광고판에 보이는 문자열 - 1 - 가능한 광고의 길이 중 가장 짧은 것의 길이 2. 재정의 문자열이 주어졌을 때 최소 반복 주기를 구하여라. 3. 해결 방법 KMP failure function을 구한다. L - failure function[last index]가 가능한 광고의 길이중 가장 짧은 것.(정당성 증명은 생략)..

1. 문제 상근이는 두 시계 사진을 가지고 있다. 각 사진은 동일한 길이와 목적을 가진 n개의 시곗바늘을 가지고 있는데 각 시곗바늘의 위치만 구분할 수 있고 가리키는 곳이 어디인지는 알 수 없다. 이때 한 시계 사지을 돌려 다른 시계 사진과 일치시킬 수 있는지를 확인하시오. -1- 바늘의 수 \(n(2 \leq n \leq 200,000)\) -2, 3- n개의 상수 \(a_{i}(0 \leq a_{i} < 360,000)\)이 주어지며 이는 각 사진에서 바늘의 시계 각도를 나타낸다. 바늘의 각도는 특정 순서대로 주어지지 않으며 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다. 두 시계 사진이 돌려서 같다면 possible을, 그렇지 않다면 impossible을 출력하라. 2. 재정의 문자열이 순환..

#include #include #include using namespace std; int cnt; string text, pattern; vector Fail() { int m = pattern.length(); vector pi(m); pi[0]=0; for(int i=1, j=0; i0 && pattern[i]!=pattern[j]) j=pi[j-1]; if(pattern[i] == pattern[j]) pi[i] = ++j; } return pi; } vector KMP() { int m = pattern.length(); int n = text.length(); vector pos; vector pi = Fail(); for(int i=0, j=0; i0 && text[i]!=pattern[j..