C语言给定两个字符串s和t判断s是否是t的子序列

思路：

- 定义两个指针i和j，分别指向s和t的开头。
- 遍历t，如果当前字符等于s的字符，则i和j同时后移；否则只将j后移。
- 如果i指针到达了s的末尾，则s是t的子序列；否则如果j指针到达了t的末尾，则s不是t的子序列。

代码实现：

bool isSubsequence(char * s, char * t){
    int i = 0, j = 0;
    while (s[i] && t[j]) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    return !s[i];
}

时间复杂度：$O(n)$，其中$n$为$t$的长度。

相关问题

用C语言编写代码，给定两个字符串S和T，保证S的长度不小于T的长度，问至少修改S的多少个字符，可以令T成为S的子序列，输入，第一行字符串S第二行字符串T，输出一个非负整数，表示需要变换的次数

在C语言中，你可以通过动态规划的方法解决这个问题。这个问题可以转化为求解最长公共前缀的长度，但实际上我们需要找到T能在S中变成子序列所需的最少改变次数。一种常见的算法是KMP（Knuth-Morris-Pratt）匹配或者Manacher's Algorithm，但这里我们可以简化为遍历S，并检查每个位置的字符是否匹配，如果不匹配则计数。

以下是一个简单的C语言函数示例，它实现了这个逻辑：

#include <stdio.h>
#include <string.h>

int min_changes(char *str1, char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int count = 0;

    for (int i = 0; i <= len1; ++i) {
        if (i > len2 || str1[i] != str2[len2 - 1]) {
            count++;
        }
        str2--; // Move to previous character in T
    }

    return count;
}

int main() {
    char S[100], T[100];
    scanf("%s %s", S, T);
    printf("至少需要修改的字符次数: %d\n", min_changes(S, T));
    return 0;
}

在这个程序中，我们从S的第一个字符开始比较，如果T还有剩余字符并且不匹配，我们就增加计数器。然后我们在T中回退一位，继续寻找下一个可能匹配的位置。

问题 1：最长公共子序列（LCS）给定两个字符串 X 和 Y，找出它们的最长公共子序列的长度。最长公共子序列是指两个序列的公共子序列中长度最长的一个。输入：两个字符串 X 和 Y（长度不超过 100）用c语言实现

在C语言中，可以使用动态规划（Dynamic Programming）算法来解决最长公共子序列（LCS）问题。这里给出一个简单的递推函数实现：

#include <stdio.h>
#include <string.h>

int lcs(char *X, char *Y, int m, int n) {
    int L[m + 1][n + 1];
    int i, j;

    // 初始化第一行和第一列
    for (i = 0; i <= m; i++) {
        L[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        L[0][j] = 0;
    }

    // 动态填充L数组
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    return L[m][n]; // 返回最长公共子序列的长度
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";    
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d\n", lcs(X, Y, m, n));
    return 0;
}

在这个代码中，`lcs()` 函数计算了 `X` 和 `Y` 的最长公共子序列长度，并通过 `max()` 函数处理 `X[i - 1]` 与 `Y[j - 1]` 不相等的情况。