Chuỗi con duy nhất trong chuỗi bao quanh trong C ++

Giả sử chúng ta có chuỗi s là chuỗi bao quanh vô hạn của "abcdefghijklmnopqrstuvwxyz", vì vậy giá trị s sẽ giống như sau - "... zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabzab P>

Bây giờ chúng ta có một chuỗi p khác. Công việc của chúng ta là tìm xem có bao nhiêu chuỗi con không rỗng duy nhất của p trong s. Cụ thể, đầu vào của chúng ta là chuỗi p và chúng ta cần xuất ra số lượng các chuỗi con không rỗng khác nhau của p trong chuỗi s.

Vì vậy, nếu đầu vào là “zab” thì đầu ra sẽ là 6. Có 6 chuỗi con “z”, “a”, “b”, “za”, “ab”, “zab” của chuỗi “zab” trong chuỗi s

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Tạo một mảng dp có kích thước 26, đặt x:=0

• cho I trong phạm vi từ 0 đến kích thước của p

  • nếu i> 0 và (p [i] - p [i - 1] là 1 hoặc p [i - 1] - p [i] là 25), thì tăng x lên 1, nếu không thì đặt x:=1

  • dp [p [i] - ASCII của ‘a’]:=tối đa của (x, dp [p [i] - ASCII của ‘a’])

• ret:=0

• cho tôi trong phạm vi từ 0 đến 25

  • ret:=ret + dp [i]

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"zab"

Đầu ra

6