字符串采用顺序存储结构，设计求子串的算法

1. 首先输入原字符串和子串，确定它们的长度。
2. 从原字符串的第一个字符开始，依次比较原字符串和子串的每个字符是否相等。
3. 如果相等，则继续比较下一个字符，直到子串的最后一个字符。
4. 如果子串的所有字符都与原字符串中的一段连续字符相等，则找到了子串，返回该子串在原字符串中的起始位置。
5. 如果子串的某个字符与原字符串中的某个字符不相等，则从原字符串的下一个字符开始重新比较，直到找到子串或者原字符串遍历完毕。
6. 如果原字符串遍历完毕仍未找到子串，则说明原字符串中不存在该子串。

相关问题

字符串采用顺序存储结构，设计求子串的算法；

假设原字符串为str，子串为substr，其长度为len_sub。

1. 首先判断substr的长度是否小于等于str的长度，如果不是，则不存在子串，直接返回空。

2. 然后从str的第一个字符开始遍历，以当前字符作为子串的起始字符，判断接下来的len_sub个字符是否与substr相同。

3. 如果相同，则找到了一个子串，记录其起始位置并将其存入结果数组中。

4. 如果不同，则继续遍历str的下一个字符，以此类推直到遍历完整个字符串。

5. 最后返回结果数组，即为所有子串的起始位置。

代码实现如下：

vector<int> findSubstr(string str, string substr) {
    vector<int> res;
    int len_str = str.length(), len_sub = substr.length();
    if (len_sub > len_str) return res;
    for (int i = 0; i <= len_str - len_sub; i++) {
        bool flag = true;
        for (int j = 0; j < len_sub; j++) {
            if (str[i+j] != substr[j]) {
                flag = false;
                break;
            }
        }
        if (flag) res.push_back(i);
    }
    return res;
}

字符串采用链式存储结构，设计求子串的算法；代码

以下是一个求子串的算法，采用了链式存储结构。

// 定义链表节点结构体
typedef struct ListNode {
    char data;
    struct ListNode* next;
} ListNode;

// 定义链表结构体
typedef struct {
    ListNode* head;
    int length;
} LinkedList;

// 初始化链表
void initLinkedList(LinkedList* list) {
    list->head = NULL;
    list->length = 0;
}

// 在链表尾部插入元素
void insertNode(LinkedList* list, char data) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    node->next = NULL;
    if (list->head == NULL) {
        list->head = node;
    } else {
        ListNode* p = list->head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = node;
    }
    list->length++;
}

// 从链表中删除指定位置的节点
void deleteNode(LinkedList* list, int index) {
    if (index < 0 || index >= list->length) {
        return;
    }
    if (index == 0) {
        ListNode* p = list->head;
        list->head = p->next;
        free(p);
    } else {
        ListNode* p = list->head;
        for (int i = 0; i < index - 1; i++) {
            p = p->next;
        }
        ListNode* q = p->next;
        p->next = q->next;
        free(q);
    }
    list->length--;
}

// 求子串
LinkedList* getSubString(LinkedList* list, int start, int end) {
    if (start < 0 || start >= list->length || end < 0 || end >= list->length || start > end) {
        return NULL;
    }
    LinkedList* subList = (LinkedList*)malloc(sizeof(LinkedList));
    initLinkedList(subList);
    ListNode* p = list->head;
    for (int i = 0; i < start; i++) {
        p = p->next;
    }
    for (int i = start; i <= end; i++) {
        insertNode(subList, p->data);
        p = p->next;
    }
    return subList;
}

使用示例：

int main() {
    LinkedList list;
    initLinkedList(&list);
    insertNode(&list, 'a');
    insertNode(&list, 'b');
    insertNode(&list, 'c');
    insertNode(&list, 'd');
    insertNode(&list, 'e');
    LinkedList* subList = getSubString(&list, 1, 3);
    ListNode* p = subList->head;
    while (p != NULL) {
        printf("%c ", p->data);
        p = p->next;
    }
    return 0;
}

输出结果：

b c d