문자열 hashing function 빠르게 계산하는 방법

1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기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 stringdeepdata.tistory.com  두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..

• format_list_bulleted 알고리즘/문자열 알고리즘
• · 2024. 5. 18.
• textsms

부분문자열 필수 트릭 - doubling cyclic substring trick

24597번: Reversibly Cyclic Strings (acmicpc.net)  문자열 s의 cyclic substring이라는 것은 s를 rotate했을때 부분문자열 t를 말한다. 'fatcat'에서 'atf'는 fatcat에서 왼쪽으로 1칸 rotate하면 atcatf인데 여기에 부분문자열로 있다 만약 s의 모든 부분문자열 t에 대하여 t를 뒤집은 것이 s의 cyclic substring이라면 s를 'Internally Reversibly Cyclic'이라고 정의한다. 주어진 s가 Internally Reversibly Cyclic인지 판단하는 문제  어떤 부분 문자열 t가 s의 cyclic substring이라는 것을 어떻게 알 수 있을까? 한칸 한칸씩 roate해서 판단해봐야할까? fatc..

• format_list_bulleted 알고리즘/문자열 알고리즘
• · 2024. 5. 9.
• 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

z - function 활용법1 -패턴이 문자열에서 몇번이나 나왔는가? 찾는법-

1. 부분문자열 검색 z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다. 이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자. 여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다. 이제 s에 대한 z-function을 계산하자. [0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다. 문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로, 이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다. 2. 연습문제 17..

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

문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 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