이 튜토리얼에서는 주어진 문자열의 회문 부분 문자열 쿼리를 풀어야 합니다. 회문 하위 문자열 쿼리를 해결하는 것은 C++에서 일반 쿼리를 해결하는 것보다 훨씬 더 복잡합니다. 훨씬 더 복잡한 코드와 논리가 필요합니다.
이 자습서에서는 문자열 str 및 Q 수의 substring[L...R] 쿼리를 제공하며, 각각은 두 개의 값 L과 R을 갖습니다. 우리는 쿼리를 해결하여 substring[L. ..R] 회문입니다. L부터 R까지의 범위 내에서 형성된 부분 문자열이 각각의 질의를 풀기 위한 회문인지 아닌지를 결정해야 한다. 예를 들어 -
Let's input "abbbabaaaba" as our input string. The queries were [3, 13], [3, 11], [5, 8], [8, 12] It is necessary to determine whether the substring is a plaindrome A palindrome is "abaaabaaaba" (3, 13) . It is not possible to write "baaa" as a palindrome [3, 11]. As in [5, 8]: "aaab" cannot be a palindrome. There is a palindrome in "baaab" ([3, 12]).
해결책을 찾기 위한 접근 방식
순진한 방법
여기서 부분 문자열이 인덱스 범위 L부터 R까지인지 확인하여 회문을 찾아야 합니다. 따라서 모든 부분 문자열 쿼리를 하나씩 확인하고 회문인지 여부를 판별해야 합니다. Q 쿼리가 있고 각 쿼리는 응답하는 데 0(N) 시간이 걸립니다. 최악의 경우 0(Q.N) 시간이 걸립니다.
예시
#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
int i, length;
int flag = 0;
length = str.length();
for(i=0;i < length ;i++){
if(str[i] != str[length-i-1]) {
flag = 1; break;
}
}
if (flag==1)
return 1;
return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
for(int i = 0; i < Q; i++){
isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"Palindrome\n":cout<<"Not palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} 출력
Palindrome Palindrome Not palindrome!
동적 프로그래밍 방식
동적 프로그래밍 접근 방식을 사용하여 문제를 해결하는 것은 효율적인 옵션입니다. 이 문제를 해결하려면 하위 문자열[i...j]이 DP[i][j]에 대한 회문인지 여부를 나타내는 부울 값을 포함하는 2차원 배열인 DP 배열을 만들어야 합니다.
이 DP 매트릭스가 생성되고 각 쿼리에 대한 모든 L-R 값이 확인됩니다.
예시
#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
int length = str.size();
int i, j;
for (i = 0; i < length; i++) {
for (j = 0; j < length; j++)
DP[i][j] = 0;
}
for (j = 1; j <= length; j++) {
for (i = 0; i <= length - j; i++) {
if (j <= 2) {
if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = 1;
}
else if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = DP[i + 1][i + j - 2];
}
}
}
void solveAllQueries(string str, int Q, int query[][2]){
int DP[50][50];
computeDP(DP, str);
for(int i = 0; i < Q; i++){
DP[query[i][0] - 1][query[i][1] - 1]?cout
<<"not palindrome!\n":cout<<"palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} 출력
palindrome! not palindrome! palindrome!
결론
이 자습서에서는 C++ 코드와 함께 회문 하위 문자열 쿼리를 해결하는 방법을 배웠습니다. 우리는 또한 자바, 파이썬 및 기타 언어로 이 코드를 작성할 수 있습니다. 이 코드는 가장 복잡하고 긴 코드 중 하나였습니다. 회문 쿼리는 일반 하위 문자열 쿼리보다 어렵고 매우 정확한 논리가 필요합니다. 이 튜토리얼이 도움이 되기를 바랍니다.