1. 반복되는 부분 문자열 찾기 전체 문자열에서 적어도 두번 이상 나타나는 부분문자열 보통 "가장 긴 반복 부분 문자열"을 찾는 것에 관심 있다 예를 들어 "abcefgabc"에서 "abc"가 두번 나타나면서, 가장 긴 반복 부분 문자열이다. 찾는 방법은 생각보다 간단한데, https://en.wikipedia.org/wiki/Substring Substring - Wikipedia From Wikipedia, the free encyclopedia Not to be confused with subsequence, a generalization of substring. "string" is a substring of "substring" In formal language theory and compute..
1. 최적화 이전 문자열 자료구조 suffix array를 만드는 manber-myers 알고리즘은 $O(Nlog^{2}N)$의 시간복잡도를 가진다. https://deepdata.tistory.com/967 문자열 핵심 자료구조 suffix array와 lcp(longest common prefix)배열 구하는법 배우기(Manber-Myers, kasai) https://cp-algorithms.com/string/suffix-array.html#definition Suffix Array - Algorithms for Competitive Programming Suffix Array Definition Let $s$ be a string of length $n$. The $i$-th suffix of ..
https://cp-algorithms.com/string/suffix-array.html#definition Suffix Array - Algorithms for Competitive Programming Suffix Array Definition Let $s$ be a string of length $n$. The $i$-th suffix of $s$ is the substring $s[i \ldots n - 1]$. A suffix array will contain integers that represent the starting indexes of the all the suffixes of a given string, after the aforemen cp-algorithms.com https:/..
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..
String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing strings efficiently. The brute force way of doing so is just to compare the letters of both strings, which has a time complexity of $O(\mi cp-algori..
1. 문제 16163번: #15164번_제보 (acmicpc.net) 16163번: #15164번_제보 www.acmicpc.net 2. 풀이 연속인 부분문자열에서 회문의 개수를 구하는 문제 manacher 알고리즘을 수행하면서, 나타나는 회문의 개수를 세면 될 것이다... 그런데 회문의 개수를 어떻게 세야할까 예를 들어 ABCBA에 대해서.. manacher 알고리즘을 수행하기 위해 #을 붙여가지고 #A#B#C#B#A#으로 바꾸고 나서.. 각 index에 대해서 양쪽으로 확대해나가 회문인지 찾아나갈텐데 A배열은 각 위치에서 가장 긴 회문의 반지름 길이를 나타내는 것으로, 가장 긴 회문의 반지름 길이를 알고 있다면, 이는 그보다 작은 회문도 포함하고 있는거니까, 이 값을 이용한다면 해당 지점에서 회문의 ..
