C++의 랩어라운드 문자열에 있는 고유한 하위 문자열

문자열 s가 "abcdefghijklmnopqrstuvwxyz"의 무한 랩어라운드 문자열이라고 가정하고 값 s는 다음과 같이 보일 것입니다 - "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...". 피>

이제 다른 문자열 p가 있습니다. 우리의 임무는 p의 비어 있지 않은 고유한 하위 문자열이 s에 몇 개 있는지 찾는 것입니다. 특히, 우리의 입력은 문자열 p이고 우리는 문자열 s에서 p의 비어 있지 않은 다른 부분 문자열의 수를 출력해야 합니다.

따라서 입력이 "zab"와 같으면 출력은 6이 됩니다. 문자열 "zab"의 6개의 부분 문자열 "z", "a", "b", "za", "ab", "zab" 문자열 s

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

크기가 26인 배열 dp를 만들고 x :=0
으로 설정합니다.
범위 0에서 p 크기까지의 I에 대해
- i> 0이고 (p[i] – p[i – 1]이 1이거나 p[i – 1] – p[i]가 25이면) x를 1만큼 증가시키고 그렇지 않으면 설정 x :=1
- dp[p[i] – 'a'의 ASCII] :=최대 (x, dp[p[i] – 'a'의 ASCII])
렛 :=0
0에서 25 사이의 I에 대해
- 렛 :=렛 + dp[i]
리턴 렛

예시(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"