Các Chuỗi Con Duy Nhất Trong Chuỗi Vòng Trong C++

Giả sử chuỗi s là chuỗi vòng vô hạn của "abcdefghijklmnopqrstuvwxyz", tức là s trông như "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Cho chuỗi p khác. Nhiệm vụ là tìm số lượng chuỗi con không rỗng duy nhất của p xuất hiện trong s. Đầu vào là chuỗi p, đầu ra là số lượng chuỗi con khác nhau của p trong s.

Ví dụ, p = "zab", đầu ra = 6. Các chuỗi con: "z", "a", "b", "za", "ab", "zab".

Để giải quyết, chúng ta làm theo các bước:

• Tạo mảng dp kích thước 26, x := 0.

• Với i từ 0 đến độ dài p:

  • Nếu i > 0 và (p[i] - p[i-1] == 1 hoặc p[i-1] - p[i] == 25), tăng x lên 1, ngược lại x := 1.

  • dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']).

• ret := 0.

• Với i từ 0 đến 25: ret += dp[i].

• Trả về ret.

Ví dụ (C++)

Hãy xem 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;
    }
};

int main(){
    Solution ob;
    cout << (ob.findSubstringInWraproundString("zab"));
}

Đầu vào

"zab"

Đầu ra

6