문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기

1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n이 될텐데 일반적으로 잘 정의하지 않는다. z[0] = 0으로 정의하기도 하고 문제에 따라 필요하다면 z[0] = n으로 정의하기도 한다. 예를 들어 'abacaba'에 대하여... z[1]은 'abacaba'와 'bacaba'의 최대 공통 접두사의 길이로... 공통 접두사가 존재하지 않으니 0 z[2]는 'abacaba'와 'acaba'의 최대 공통 접두사의 길이로 'a'가 있으니 z[2] = 1 z[3]은 'abacaba'와 'caba'의 최대 공통 접두사의 길이로..

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

suffix array 깊이 이해하기 2 -부분 문자열의 개수를 세는 방법-

1. 문제1 11479번: 서로 다른 부분 문자열의 개수 2 (acmicpc.net) 11479번: 서로 다른 부분 문자열의 개수 2 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000,000 이하이다. www.acmicpc.net 2. 풀이 1) "모든 부분 문자열은 접미사들의 접두사이다" suffix array를 구한다면 suffix_array[i]는 사전순으로 오름차순 정렬된 i번째 접미사의 위치를 알 수 있다 그러면 문자열의 길이가 n이라면 i번째 접미사의 길이는 얼마일까? 당연히 n - suffix_array[i]이다. "ABAAB"에 대하여 suffix array를 생각해보자. index suffix array 2 AAB 3 AB 0 ABAAB 4 B 1..

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

문자열 핵심 자료구조 suffix array O(NlogN) 최적화 배우기

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 ..

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

문자열 핵심 자료구조 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 $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:/..

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