blog.koderpark.dev/145 백준 BOJ 3033 & 1605 - 가장 긴 문자열 & 반복 부분문자열 둘이 동일한 문제라 이것도 깔끔하게 날먹했다. 이 문제는 Suffix Array와 LCP를 구현하는 문제이다 LCP의 최댓값이 바로 문제에서 원하는 정답. www.acmicpc.net/problem/3033 3033번: 가장 긴 문자열 첫째 줄 blog.koderpark.dev 와 97%쯤 동일한 문제 저기서는 LCP의 최댓값을 요구하고 있고, 이 문제는 LCP와 Suffix Array를 동시에 출력해주면 된다. www.acmicpc.net/problem/9248 9248번: Suffix Array Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들..
둘이 동일한 문제라 이것도 깔끔하게 날먹했다. 이 문제는 Suffix Array와 LCP를 구현하는 문제이다 LCP의 최댓값이 바로 문제에서 원하는 정답. www.acmicpc.net/problem/3033 3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net www.acmicpc.net/problem/1605 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net 배열이 상상히..
마나커/마나허/manacher's 알고리즘을 구현하는 문제이다 똑같은 문제가 두개 있어서 깔끔하게 날먹했다. www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 마나허 알고리즘이 NYPC예선문제 풀때도 나왔었던거 같은데 그..
아호-코라식 구현 문제. ㅇㄴ 왜이렇게 소스코드가 길까요 이 알고리즘은 구현하는데 진이 다빠진 문제였다. www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net 아호코라식에 딸려오는 선행개념이 트라이 자료구조가 있는데, 한번 찾아보고 오면 소스코드 이해가 훨씬 쉬울 거 같다. #include #include #include using namespace std; struct TRIE{ TRIE* alpha[26]; TRIE* fail; bool ans; TRI..
KMP 알고리즘을 구현하면 되는 문제 지문에서 친절하게 힌트를 주고 있다. www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 겨울학교 출제 문제는 입력이 상당히 까다롭게 주어져서 솔직히말하면 KMP라는 알고리즘 자체의 구현보다 입력 깔끔하게 받기에 더 많은 신경을 쓴 거 같다..... #include #include #include #include using namespace std; char s1[1234567]; char s2[1234567]; int..
세그멘트 트리 레이지 프로퍼게이션 문제. 이것 역시 겨울학교에서 복붙했다 ㅋㅋ www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지세그는 갱신을 필요할때만 하게끔 따로 propergate()라는 함수를 작성해주는데, 이것이 구간쿼리를 더 빠르게 처리할 수 있게 해준다. #include #include #include #define MID ((s+e)/2) using namespace std; int seg[456789..