Chương trình kiểm tra chuỗi là dãy con của chuỗi khác trong C++

Giả sử có hai chuỗi S và T. Ta phải kiểm tra xem S có phải là dãy con (subsequence) của T hay không.

Vì vậy, nếu đầu vào là S = "abc", T = "adbrcyxd", thì đầu ra sẽ là True.

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

• nếu s giống t, thì trả về true
• n := kích thước s, m := kích thước t
• j := 0
• với i := 0, khi i < n, tăng i 1, làm:
• nếu t[j] giống s[i], thì tăng j 1
• nếu j bằng kích thước t, thì trả về true
• trả về false

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(string t, string s) {
        if(s == t) return true;
        int n = s.size();
        int m = t.size();
        int j = 0;
        for(int i = 0; i < n; i++) {
            if(t[j] == s[i]) j++;
            if(j == t.size()) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    string S = "abc", T = "adbrcyxd";
    cout << ob.solve(S, T);
    return 0;
}

Đầu vào

"abc", "adbrcyxd"

Đầu ra

1