누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉

1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$ 을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 2. 12.
• textsms

z function 활용법 2 - prefix이면서 suffix인 문자열을 찾는 방법-

1. border 어떤 문자열의 prefix이면서 동시에 suffix이기도 한 부분문자열을 border라고 부른다. 이 border와 관련된 문제를 해결하는데 z function이 매우 강력하다. z function의 정의에 대해 생각해본다면.. z[i]는 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 뜻한다 https://deepdata.tistory.com/1000 문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기 1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n deepda..

• format_list_bulleted 문자열 알고리즘
• · 2023. 9. 28.
• textsms

KMP(Knuth–Morris–Pratt) 알고리즘 배우고 부분문자열 검색하는 방법 익히기

https://cp-algorithms.com/string/prefix-function.html Prefix function - Knuth-Morris-Pratt - Algorithms for Competitive Programming Prefix function. Knuth–Morris–Pratt algorithm Prefix function definition You are given a string $s$ of length $n$. The prefix function for this string is defined as an array $\pi$ of length $n$, where $\pi[i]$ is the length of the longest proper prefix cp-algorithms..

• format_list_bulleted 문자열 알고리즘
• · 2023. 8. 10.
• textsms