문자열 str이 주어집니다. 목표는 특수 회문이고 길이가 1보다 큰 str의 모든 하위 문자열을 계산하는 것입니다. 특수 회문은 모두 동일한 문자 또는 중간 문자만 다른 문자열입니다. 예를 들어 문자열이 "baabaa"이면 원본의 하위 문자열인 특수 회문은 "aa", "aabaa", "aba", "aa"입니다.
예를 들어 이해합시다.
입력 - str="abcccddf"
출력 − 문자열의 특수 회문 수는 − 3입니다.
설명 − 특수 회문인 부분 문자열은 − "cc", "cdc", "dcd"
입력 − str="바바압"
출력 − 문자열의 특수 회문 수는 − 4입니다.
설명 − 특수 회문인 부분 문자열은 − "aa", "aabaa", "aba", "aa"입니다.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
알파벳 문자열을 만들고 길이를 계산합니다. 추가 처리를 위해 데이터를 함수에 전달합니다.
-
임시 변수 count와 i를 선언하고 0으로 설정
-
문자열 크기의 배열을 만들고 0으로 초기화합니다.
-
i가 문자열 길이보다 작아질 때까지 WHILE 시작
-
while 내부에서 변수를 total로 1로 설정하고 변수 j를 i + 1로 설정
-
str[i] =str[j] AND j가 문자열 길이보다 작을 때까지 WHILE을 다시 시작합니다.
-
while 내부에서 합계를 1씩, j를 1씩 증가
-
카운트를 count + ( total * (total + 1) / 2로 설정하고 arr[i]를 total로, i를 j
로 설정합니다. -
문자열 길이까지 j에서 1까지 FOR 루프 시작
-
str[j] =str[j-1]인지 확인한 다음 arr[j]를 arr[j-1]
로 설정합니다. -
변수 temp를 str[j-1]로 설정하고 j> 0 AND j <문자열 길이 AND temp =str[j+1] AND sr[j]!=temp인지 확인한 다음 count를 count +로 설정합니다. 최소(arr[j-1], arr[j+1])
-
개수 설정 - 문자열 길이
-
개수 반환
-
결과를 인쇄하십시오.
예
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len){
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len){
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++){
if (str[j] == str[j - 1]){
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main(){
string str = "bcbaba";
int len = str.length();
cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of special palindromes in a String are: 3