C++로 풀어보는 순환 문자열(Wraparound String) 속 고유한 부분 문자열 개수 구하기

문제 이해하기

문자열 s를 알파벳 "abcdefghijklmnopqrstuvwxyz"가 무한히 반복되는 순환(wraparound) 문자열이라고 가정해 보겠습니다. 이때 s는 다음과 같은 형태를 갖습니다.

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."

이제 또 다른 문자열 p가 주어졌을 때, p의 고유한(중복되지 않는) 비어 있지 않은 부분 문자열 중 문자열 s에 포함되는 것의 개수를 구하는 것이 우리의 과제입니다. 즉, 입력으로 문자열 p가 주어지면, p의 서로 다른 비어 있지 않은 부분 문자열들 중 s 안에 실제로 존재하는 것들의 개수를 출력해야 합니다.

예를 들어 입력이 "zab"라면 출력은 6이 됩니다. 문자열 "zab"의 부분 문자열인 "z", "a", "b", "za", "ab", "zab" 여섯 개가 모두 순환 문자열 s 안에 포함되기 때문입니다.

해결 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

크기가 26인 배열 dp를 생성하고, 변수 x를 0으로 초기화합니다.
i를 0부터 p의 길이까지 반복합니다.
- i > 0이고 (p[i] − p[i−1] == 1 또는 p[i−1] − p[i] == 25)이면 x를 1 증가시키고, 그렇지 않으면 x := 1로 설정합니다.
- dp[p[i] − 'a']를 max(x, dp[p[i] − 'a']) 값으로 갱신합니다.
ret := 0으로 초기화합니다.
i를 0부터 25까지 반복하며 ret에 dp[i]를 더합니다.
ret을 반환합니다.

여기서 핵심 아이디어는 다음과 같습니다. 순환 문자열 s에는 알파벳이 연속적으로 이어지는 부분 문자열만 존재할 수 있습니다. 따라서 p를 순회하며 현재 위치에서 끝나는 연속 증가 구간의 길이를 x로 추적하고, 각 알파벳 문자별로 해당 문자로 끝나는 가장 긴 연속 구간의 길이를 dp에 저장합니다. 같은 문자로 끝나는 부분 문자열끼리는 서로 중복될 수 있으므로 최댓값만 유지하면 되고, 길이가 L인 연속 구간은 길이 1부터 L까지 정확히 L개의 고유한 부분 문자열을 만들어냅니다. 마지막으로 dp 배열의 모든 값을 합산하면 정답을 얻을 수 있습니다.

C++ 예제 코드

아래 구현을 살펴보면 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findSubstringInWraproundString(string p) {
      vector <int> dp(26);
      int x = 0;
      for(int i = 0; i < p.size(); i++){
         if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
            x++;
         }
         else x = 1;
         dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
      }
      int ret = 0;
      for(int i = 0; i < 26; i++){
         ret += dp[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findSubstringInWraproundString("zab"));
}

입력

"zab"