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..
C++17 백준 컴파일러가 gets를 지원 안해서 좀 골치아픈 문제. fgets로 해결했다 일단. www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net fgets를 통해 문자열을 받고 단어가 등장하는걸 확인한 경우에는 단어의 길이만큼 인덱스를 건너뛰게 하는 방법으로 중복을 막았다. #include #include #include char arr[3456] = {0}; char input[123] = {0}; bool compare(int idx, char *s1, ch..