블로그 옮겼습니다

http://codeforces.com/contest/535/problem/D 길이가 n인 어떤 문자열 s 가있고, 이 s안에서 k번 등장하는 어떤 패턴 p가 있다.패턴 p가 등장하는 위치를 오름차순으로 정렬한 sequence 에서 m개의 숫자로 이루어진임의의 subsequence 를 sub 이라고하자.입력으로 n, m, p, sub 가 주어질 때, 가능한 원래의 문자열 s의 가짓수를 구하는 문제이다.\(1 \le n \le 10^6\)\(0 \le m \le n - |p| + 1\)\(1 \le |p| \le n\) 우선, 길이 n인 연속된 빈 칸을 생각해 보자 여기에 p가 등장하는 위치에 p를 넣고 난 뒤빈 칸의 개수를 x라고 할 때 \(26^x\) 를 \(10^9+7\) 로 나눈 나머지를 구하는 문..

Z algorithm 은 문자열관련 알고리즘이다. 우선 Z Array 라는 것이 있다. Z[i] 의 정의는 아래와 같다. Z[i] : S[i...] 의 prefix 들 중 S의 prefix이기도 한 녀석들 중 길이가 가장 긴녀석의 길이즉, i에서 시작하는 S의 부분 문자열들 중 S의 prefix 이기도 한 녀석들 중 가장 긴 길이이다. 이 Z Array 를 O(|S|) 의 시간에 구할 수 있게 해주는 것이 Z algorithm 이다. 우선 이 것을 알면 KMP와 같이 문자열 검색이 선형시간에 가능하다. 즉, 어떤 긴 문자열 S에서 특정 패턴 P가 등장하는 위치를 모두 구하는 것이 Z 알고리즘을 활용하여 O(S + P) 에 가능한데 이 방법은 나중에 아래에서 설명하겠다. 그리고 가끔 이런 문제들이 있다. ..

https://algospot.com/judge/problem/read/COUNTPALIN \( 1\leq{N}\leq{10^6} \)길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해최대..

https://community.topcoder.com/stat?c=problem_statement&pm=11514 \(1\leq{N}\leq{50}\)\(1\leq{C}\leq{N}\)\(1\leq{L}\leq{50}\)문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..