C++의 회문 하위 문자열 쿼리

이 튜토리얼에서는 주어진 문자열의 회문 하위 문자열 쿼리를 풀어야 합니다. 회문 하위 문자열 쿼리를 해결하는 것은 C++에서 일반 쿼리를 해결하는 것보다 훨씬 더 복잡합니다. 더 복잡한 코드와 논리가 필요합니다.

이 튜토리얼에서는 각각 L과 R의 두 값을 갖는 문자열 str 및 Q 하위 문자열 [L...R] 쿼리를 제공했습니다. 우리의 목표는 하위 문자열[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]).

Solution method

Naive method

여기서 부분 문자열이 인덱스 범위 L에서 R 사이에 있는지 확인하여 회문을 찾아야 합니다. 따라서 모든 부분 문자열에 대해 쿼리를 수행해야 합니다. 그것이 회문인지 확인하기 위해. Q 쿼리가 있으므로 각 쿼리에 응답하는 데 0(N) 시간이 걸립니다. 최악의 경우 0(Q.N) 시간이 걸린다.

Example

#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;
}

Output

Palindrome
Palindrome
Not palindrome!

동적 프로그래밍 방법

동적 프로그래밍 방법을 사용하여 문제를 해결하는 것은 효과적인 선택입니다. 이 문제를 해결하려면 DP 배열을 만들어야 합니다. DP 배열은 하위 문자열[i...j]가 DP[i][j]의 회문인지 여부를 나타내는 부울 값을 포함하는 2차원 배열입니다.

는 이 DP 매트릭스를 생성하고 각 쿼리에 대한 모든 L-R 값을 확인합니다.

Example

#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;
}

Output

palindrome!
not palindrome!
palindrome!

Conclusion

이 튜토리얼에서는 C++ 코드를 사용하여 회문 하위 문자열 쿼리를 해결하는 방법을 배웠습니다. 이 코드를 Java, Python 및 기타 언어로 작성할 수도 있습니다. 이 코드는 가장 복잡하고 장황한 코드 중 하나입니다. Palindrome 쿼리는 일반 하위 문자열 쿼리보다 어렵고 매우 정확한 논리가 필요합니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 C++의 회문 하위 문자열 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!