문자열과 시작부터 끝까지의 범위가 주어지고 주어진 범위에 존재하는 회문 부분 문자열의 수를 계산하는 것이 작업입니다. 회문 문자열은 nitin, aba 등과 같이 문자열의 앞뒤가 유사한 문자열입니다.
예
입력 - InputString ="cccaabbbdee", 시작 =2, 끝 =6;
출력 - 인덱스 범위 7의 회문 하위 문자열 수
설명 - 범위와 문자열이 제공되므로 시작 포인터인 2 즉 'c'에서 6, 즉 'b'까지 문자열 탐색을 시작하므로 하위 문자열은 'caabb'입니다. 따라서 회문 부분 문자열은 'c', 'a', 'a', 'b', 'b', 'aa' 및 'bb'입니다. 따라서 회문 부분 문자열의 개수는 7입니다.
입력 - InputString ="lioaabbbdee", 시작 =0, 끝 =2;
출력 - 인덱스 범위 3의 회문 하위 문자열 수
설명 - 범위와 문자열이 제공되므로 시작 포인터가 0인 'l'에서 2, 즉 'o'까지 문자열 탐색을 시작하므로 하위 문자열은 'lio'입니다. 따라서 회문 부분 문자열은 'l', 'i' 및 'o'입니다. 따라서 회문 부분 문자열의 개수는 3입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 지정된 크기의 문자열을 선언하고 변수 시작부터 끝까지 범위를 지정합니다.
- 추가 처리를 위해 palindrome_index(arr, InputString)라는 함수에 데이터를 전달합니다.
- 함수 내에서 배열 크기로 확인된 다른 배열을 선언합니다.
- 0에서 배열 길이까지 루프 FOR i 시작
- 루프 내에서 0부터 배열 길이까지 또 다른 루프 FOR j 시작
- 루프 내에서 검사를 check[i][j] =0 및 arr[i][j] =0으로 설정
- 길이 - 1부터 i가 0보다 클 때까지 FOR i 루프 시작
- 루프 내에서 i의 check 및 arr을 1로 설정한 다음 i + 1에서 배열 길이까지 FOR j에 대한 또 다른 루프를 시작합니다.
- 루프 내에서 i i의 IF 문자열이 j의 문자열과 같고 i + 1이 j - 1보다 큰지 또는 check[i + 1][j - 1])이 0과 같지 않은지 확인한 다음 check[i]를 설정합니다. [j]를 1로 설정하지 않고, check[i][j]를 0으로 설정한 다음 arr[i][j] =arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + 체크[i][j]
- 2차원 배열을 시작과 끝으로 인쇄합니다.
예시
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]);
}
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of Palindromic substrings in an Index range 7