用顺序结构存储串，设计一个算法求串t在串s中不重叠出现的次数，如果不是子串则返回0，例如“aa”在”aaab”中出现的次数为2.

这道题目考察的是字符串的操作。要求设计一个算法，统计一个串t在串s中不重叠出现的次数，如果不是子串则返回0。例如，对于字符串s="aaabaaab", t="aa"，应该返回2。

可以使用双指针的思想，从字符串s的第一个字符开始逐个扫描，当扫描到一个字符与t的第一个字符相等时，就从这个位置开始比较t和s是否匹配。如果匹配成功，就计数器加一并继续扫描。否则，就把指针往后移一位，重新开始匹配。

具体实现可以使用两个指针i和j来指示当前比较的位置。如果s[i] == t[j]，就把i和j都往后移一位。如果j移动到了t的末尾，则表示匹配成功，计数器加一。此时，需要把i和j重新初始化，从下一个位置继续比较。

如果比较完了整个s，还没有找到任何匹配，就返回计数器的值。

算法的时间复杂度和空间复杂度都是O(n)，其中n为串s的长度。

相关问题

假设串采用顺序串存储结构。设计一个算法求串t在串s中出现的次数，如果不是子串返回0。基于BF算法求解。例如"aa"在"aaaab"中出现2次。用C语言

当我们在顺序串（如字符数组）中查找一个子串 t 的出现次数时，可以使用暴力匹配或叫做“Brute Force”（简单遍历）的方式来实现。这里我们可以基于朴素搜索（即滑动窗口法）的概念，结合 Boyer-Moore 算法的思想，但这里我们更偏向于简单的遍历。

下面是使用 C 语言的一个基本版本的算法：

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

int countSubstrInStr(char *s, char *t) {
    int count = 0;
    int i, j;

    // 首先确保子串不为空
    if (!t || !*t) {
        return 0;
    }

    // 主字符串长度
    int len_s = strlen(s);
    // 子字符串长度
    int len_t = strlen(t);

    for (i = 0; i <= len_s - len_t; i++) { // 滑动窗口从0开始到len_s-len_t
        for (j = 0; j < len_t; j++) { // 对每个字符检查是否匹配
            if (s[i + j] != t[j]) {
                break; // 如果不匹配，跳过这个位置继续寻找
            }
        }
        
        // 匹配完成，说明找到了一个子串
        if (j == len_t) {
            count++;
            i += len_t - 1; // 跳过已匹配的部分，继续下一个可能的位置
        }
    }

    return count;
}

int main() {
    char s[] = "aaaab";
    char t[] = "aa";
    printf("'%s' 在 '%s' 中出现次数: %d\n", t, s, countSubstrInStr(s, t));
    return 0;
}

C语言采用顺序结构存储串,设计一个算法,求串s和串t的一个最长公共子串

C语言可以使用动态规划(Dynamic Programming)的策略来寻找两个字符串`s`和`t`的最长公共子串(LCS - Longest Common Substring)。这里是一个简单的基于二维数组的算法：

1. 定义一个大小为`(m+1) x (n+1)`的二维字符数组`dp`，其中`m`和`n`分别是`s`和`t`的长度。这个数组的每个元素`dp[i][j]`表示字符串`s`的前i个字符和`t`的前j个字符之间的最长公共子串的长度。

2. 初始化第一行和第一列，因为单个字符不可能是它们之间共同的子串，所以`dp[0][j] = dp[i][0] = 0`，表示没有匹配。

3. 遍历`dp`矩阵，对于每个位置`(i, j)`，如果`s[i]`等于`t[j]`，则`dp[i][j] = dp[i-1][j-1] + 1`，因为它找到了一个新的匹配字符，最长公共子串长度加一。如果`s[i]`不等于`t[j]`，则`dp[i][j] = 0`，意味着当前字符无法构成新的公共子串。

4. 当遍历结束后，`dp[m][n]`即为最长公共子串的长度。为了获取实际的子串，从`s`的末尾开始，向前回溯`dp`矩阵，记录下每个匹配的位置，直到找到`dp[m][n]`步长的子串。

下面是伪代码形式的实现：

function longest_common_substring(s, t):
    m = length(s)
    n = length(t)
    dp = array(m+1, n+1, 0)

    max_len = 0
    end_index = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_index = i
            else:
                dp[i][j] = 0

    return s[end_index-max_len:end_index]

# 示例：s = "ABCDGH", t = "AEDFHR"
lcs = longest_common_substring("ABCDGH", "AEDFHR")