실패함수2 global round #7 D2 - Prefix-Suffix Palindrome (실패함수, prefix function) https://codeforces.com/contest/1326/problem/D2 문자열 s가 주어질 때, s의 prefix a, suffix b를 이어붙여 만들 수 있는 최대길이 팰린드롬을 출력하라. (단, a+b 0 && t[i] != t[j]) j = pref[j - 1]; if (t[i] == t[j]) pref[i] = ++j; } int tt; string inp; string prefixPalin(string a) { string b = a; reverse(b.begin(), b.end()); string s = a + "#" + b;//더미문자 추가해서 s길이 홀수로 강제 vector pref(s.size()); int j = 0; for (int i = 1; i < s.size(); i.. 2020. 3. 20. BOJ 1701 - Cubeeditor (KMP, 실패함수) https://www.acmicpc.net/problem/1701 입력된 문자열에서 두 번 이상 나오는 부분 문자열의 길이중 최대를 출력하는 문제. abcabcabc 가 주어졌을 때, abc와 abcabc모두 가능하므로 둘 중 더 긴 abcabc의 길이인 6이 정답이다. 두 번 이상 나오는 부분 문자열의 길이 중 최대 -> 모든 부분 문자열 중에서 실패함수의 최대값 fail[n-1]까지 구하면서 인덱스0~1, 0~2, 0~3, ... 0~n-1 부분 문자열 중 실패함수를 모두 구할 수 있다. 따라서 시작지점이 0일때, 1일때, .... n-2일 때의 실패함수를 모두 확인해서 최대값을 출력하면 된다. #include #include #include using namespace std; const int M.. 2019. 11. 6. 이전 1 다음