C++算法：判断字符串子序列

C++算法：判断字符串子序列

以下是使用C++编写的程序，用于判断字符串B是否为字符串A的子序列：

#include <iostream>
#include <string>
using namespace std;

boolean isSubsequence(string A, string B) {
    int ptrA = 0;
    int ptrB = 0;
    
    while (ptrA < A.length() && ptrB < B.length()) {
        if (A[ptrA] == B[ptrB]) {
            ptrB++;
        }
        ptrA++;
    }
    
    return ptrB == B.length();
}

int main() {
    string A = 'BROWAHTRUDOING';
    string B = 'TRU';
    
    if (isSubsequence(A, B)) {
        cout << 'B是A的子序列' << endl;
    } else {
        cout << 'B不是A的子序列' << endl;
    }
    
    return 0;
}

在这个例子中，A的值为'BROWAHTRUDOING'，B的值为'TRU'。通过运行上述程序，可以得到输出结果为'B是A的子序列'。

代码解释:

• 该程序使用双指针方法，ptrA 指向字符串 A，ptrB 指向字符串 B。
• 遍历字符串 A，如果 A[ptrA] 等于 B[ptrB]，则 ptrB 向后移动一位。
• 如果 ptrB 最终移动到 B 的末尾，则说明 B 中所有字符都在 A 中出现过，且顺序一致，因此 B 是 A 的子序列。

该算法的时间复杂度为O(n),其中n为字符串A的长度。