主串“aabbaaaabbcc”,子串T=“aabbac”则子串T的next值为

首先，计算子串T的前缀函数值：

T： a a b b a c
next： 0 1 0 1 2 0

计算过程如下：

- next[0] = 0，因为一个字符的字符串没有前缀和后缀。
- 对于 i=1，T[0...i-1] 的前缀为 {a}，后缀为 { }，二者没有交集，因此 next[1] = 0。
- 对于 i=2，T[0...i-1] 的前缀为 {a, a}，后缀为 {a}，二者没有交集，因此 next[2] = 0。
- 对于 i=3，T[0...i-1] 的前缀为 {a, a, b}，后缀为 {b}，二者没有交集，因此 next[3] = 1。
- 对于 i=4，T[0...i-1] 的前缀为 {a, a, b, b}，后缀为 {a, b}，共有一个字符 a 和 b 相交，因此 next[4] = 1。
- 对于 i=5，T[0...i-1] 的前缀为 {a, a, b, b, a}，后缀为 { }，二者没有交集，因此 next[5] = 2。

因此，子串T的next数组为：

T： a a b b a c
next： 0 1 0 1 2 0

相关问题

用BF算法实现主串abacdacdeafadec子串acdea匹串

下面是使用BF算法实现主串abacdacdeafadec子串acdea匹配的Python代码：

def bf_match(main_str, pattern_str):
    m = len(main_str)
    n = len(pattern_str)
    for i in range(m-n+1):
        j = 0
        while j < n and main_str[i+j] == pattern_str[j]:
            j += 1
        if j == n:
            return i
    return -1

main_str = "abacdacdeafadec"
pattern_str = "acdea"
index = bf_match(main_str, pattern_str)
if index != -1:
    print("匹配成功，子串在主串中的位置为：{}".format(index))
else:
    print("匹配失败")

输出结果为：

匹配成功，子串在主串中的位置为：5

解释：从主串的第一个字符开始，依次取出与子串长度相等的子串进行比较，如果相等就返回该子串在主串中的位置。在这个例子中，我们从主串的第一个字符a开始，依次取出长度为5的子串abacd与子串进行比较，不相等；然后取出长度为5的子串bacda与子串进行比较，不相等；再取出长度为5的子串acdac与子串进行比较，不相等；接着取出长度为5的子串cdacd与子串进行比较，不相等；继续取出长度为5的子串dacde与子串进行比较，相等，返回该子串在主串中的位置5。

给一个主串和子串判断是否有子串C语言

实现：

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

int isSubstring(char *str1, char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    for(int i=0; i<=len1-len2; i++) {
        int j;
        for(j=0; j<len2; j++) {
            if(str1[i+j] != str2[j])
                break;
        }
        if(j == len2)
            return 1;
    }
    return 0;
}

int main() {
    char str1[100], str2[100];
    printf("Enter the main string: ");
    scanf("%s", str1);
    printf("Enter the substring: ");
    scanf("%s", str2);

    if(isSubstring(str1, str2))
        printf("The substring is present.\n");
    else
        printf("The substring is not present.\n");

    return 0;
}

该程序首先输入主串和子串，然后调用`isSubstring`函数来判断子串是否在主串中出现。`isSubstring`函数使用两个指针来遍历主串和子串，并比较它们的字符。如果子串中的所有字符都在主串中匹配，则`isSubstring`函数返回1，否则返回0。

示例输出：

Enter the main string: hello world
Enter the substring: world
The substring is present.