C++에서 주어진 힘으로 하위 문자열 찾기

이 문제에서는 문자열 str과 정수 pow가 제공됩니다. 우리의 임무는 주어진 힘을 가진 부분 문자열을 찾는 것입니다. .

power가 pow와 같은 부분 문자열을 반환해야 합니다.

문자열의 거듭제곱 캐릭터의 힘의 합입니다.

문자의 힘 :a -> 1, b -> 2, c -> 3,...

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : string = "programming" power = 49
Output : 'pro'

설명 -

Power of matrix : pro,
power(p) = 16
power(p) = 18
power(p) = 15
Total = 16 + 18 + 15 = 49

솔루션 접근 방식

문제에 대한 간단한 해결책은 중첩 루프를 사용하는 것입니다. 문자열을 반복하고 내부 루프를 사용하여 하위 문자열을 찾습니다. 각 부분 문자열에 대해 검정력을 계산합니다. 그런 다음 'pow'와 같은지 확인하고 맞으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

문제를 해결하기 위한 효율적인 접근 방식은 맵을 사용하여 전력을 저장하는 것입니다. 부분 문자열의 거듭제곱을 계산하여 맵에 저장합니다. 전력을 필요한 전력과 동일하게 만들 수 있는 값이 맵에 존재하는지 확인합니다. 그렇다면 true를 반환하세요. . 거짓 반환 문자열의 모든 문자가 탐색되고 일치하는 값이 없는 경우.

알고리즘

• 1단계 − 문자열을 탐색하고 거듭제곱(currPow)을 찾습니다.

• 2단계 − 지도에 (currPow - pow) 값이 존재하는지 여부.

  • 2.1단계 - 그렇다면 인쇄 -> 부분 문자열.

• 3단계 − 지도에 currPow의 값을 삽입합니다.

• 4단계 − 문자열의 모든 문자를 순회하면 출력 -> '불가능'

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
   int i;
   unordered_map<int , int > powerSS;
   int currPower = 0;
   int N = str.length();
   for (i = 0; i < N; i++) {
      currPower = currPower + (str[i] - 'a' + 1);
      if (currPower == power) {
         cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
         return;
      }
      if (powerSS.find(currPower - power) != powerSS.end()) {
         cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
         cout<<" has power "<<power; return;
      }
      powerSS[currPower] = i;
   }
   cout<<"No substring found!";
}
int main() {
   string str = "programming";
   int power = 49;
   findSubStringWithPower(str, power);
   return 0;
}

출력

Substring : pro has power 49