Computer >> Máy Tính >  >> Lập trình >> C ++

Số chuỗi con Palindromic trong một phạm vi Chỉ mục trong C ++

Chúng tôi được cung cấp một chuỗi và một phạm vi bắt đầu từ đầu đến cuối và nhiệm vụ là tính số lượng chuỗi con palindromic có trong một phạm vi nhất định. Chuỗi Palindrome là những chuỗi tương tự từ chuyển tiếp và quay lại của một chuỗi như nitin, aba, v.v.

Ví dụ

Đầu vào - InputString ="cccaabbbdee", start =2, end =6;

Đầu ra - Số chuỗi con Palindromic trong một phạm vi Chỉ mục 7

Giải thích - chúng ta được cung cấp với một phạm vi và một chuỗi vì vậy, chúng ta sẽ bắt đầu duyệt qua chuỗi từ con trỏ bắt đầu là 2 tức là 'c' cho đến 6 tức là 'b' do đó chuỗi con là 'caabb'. Vì vậy, chuỗi con palindromic là 'c', 'a', 'a', 'b', 'b', 'aa' và 'bb'. Vì vậy, số chuỗi con palindromic là 7.

Đầu vào - InputString ="lioaabbbdee", start =0, end =2;

Đầu ra - Số chuỗi con Palindromic trong một phạm vi Chỉ mục 3

Giải thích - chúng ta được cung cấp với một phạm vi và một chuỗi vì vậy, chúng ta sẽ bắt đầu duyệt qua chuỗi từ con trỏ bắt đầu là 0 tức là 'l' cho đến 2 tức là 'o' do đó chuỗi con là 'lio'. Vì vậy, chuỗi con palindromic là 'l', 'i' và 'o'. Vì vậy, số chuỗi con palindromic là 3.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Khai báo một chuỗi có kích thước nhất định bất kỳ và một phạm vi bắt đầu từ một biến bắt đầu cho đến khi kết thúc.
  • Chuyển dữ liệu đến hàm có tên palindrome_index (arr, InputString) để xử lý thêm
  • Bên trong hàm, khai báo một mảng khác có tên đã kiểm tra với kích thước mảng.
  • Bắt đầu vòng lặp FOR i từ 0 cho đến hết chiều dài của một mảng
  • Bên trong vòng lặp, bắt đầu một Vòng lặp FOR j khác từ 0 cho đến hết độ dài của một mảng
  • Trong vòng lặp, đặt kiểm tra là kiểm tra [i] [j] =0 và arr [i] [j] =0
  • Bắt đầu vòng lặp FOR tôi từ độ dài - 1 cho đến khi tôi lớn hơn 0
  • Bên trong vòng lặp, đặt kiểm tra và arr của i là 1, sau đó bắt đầu một vòng lặp FOR j khác từ i + 1 cho đến hết độ dài của một mảng
  • Bên trong vòng lặp, kiểm tra chuỗi IF tại i i bằng với chuỗi tại j VÀ i + 1 lớn hơn j - 1 HOẶC kiểm tra [i + 1] [j - 1]) không bằng 0 rồi đặt kiểm tra [i] [j] là 1 ELSE, đặt check [i] [j] là 0 rồi đặt arr [i] [j] =arr [i] [j - 1] + arr [i + 1] [j] - arr [i + 1] [j - 1] + kiểm tra [i] [j]
  • In mảng 2-D dưới dạng bắt đầu và kết thúc.

Ví dụ 

import java.io.*;
class testqwe {
   static void palindrome_index(int arr[][], String s) {
      int length = s.length();
      int[][] check = new int[length + 1][length + 1];
      for (int i = 0; i <= length; i++) {
         for (int j = 0; j <= length; j++) {
            check[i][j] = 0;
            arr[i][j] = 0;
         }
      }

      for (int i = length - 1; i >= 0; i--) {
         check[i][i] = arr[i][i] = 1;
         for (int j = i + 1; j < length; j++) {
            if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
               check[i][j] =1;
            } else {
               check[i][j] =0;
            }
            arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
         }
      }
   }
   public static void main(String args[]) {
      String InputString = "cccaabbbdee";
      int[][] arr;
      arr = new int[50][50];
      palindrome_index(arr, InputString);
      int start = 2;
      int end = 6;
      System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
   }
}

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra 

Count of Palindromic substrings in an Index range 7