C++输出串(链表）s中子串t的个数

Question

输出串s中子串t的个数，例如：s="abcabeabc",子串t="abc".个数为2.
我写了两个count函数，第一个（被注释掉的）只能输出文字，数不出来结果，
第二个一点也输不出来，应该是while循环的条件有问题。这整个count函数，我的思路都特别乱，对于条件的开始和停止都不知道如何编写。

/*********************************************************************
    程序名:
    版权:
    作者:
    日期: 2024-04-18 21:36
    说明:
*********************************************************************/
#include <iostream>
#include <malloc.h>
using namespace std;

typedef struct node {
    char data;
    struct node *next;
} LinkString;

void Assign(LinkString *&s, char str[]) {
    int i = 0;
    LinkString *p, *tc;
    s = (LinkString *)malloc(sizeof(LinkString));
    tc = s;
    while (str[i] != '\0') {
        p = (LinkString *)malloc(sizeof(LinkString));
        p->data = str[i];
        tc->next = p;
        tc = p;
        i++;
    }
    tc->next = NULL;
}

void DestroyStr(LinkString *&s) {
    LinkString *pre = s, *p = pre->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);
}

void StrCopy(LinkString *&s, LinkString *t) {
    LinkString *p = t->next, *q, *tc;
    s = (LinkString *)malloc(sizeof(LinkString));
    tc = s;
    while (p != NULL) {
        q = (LinkString *)malloc(sizeof(LinkString));
        q->data = p->data;
        tc->next = q;
        tc = q;
        p = p->next;
    }
    tc->next = NULL;
}

int StrLength(LinkString *s) {
    int n = 0;
    LinkString *p = s->next;
    while (p != NULL) {
        n++;
        p = p->next;
    }
    return n;
}

int StrEqual(LinkString *s, LinkString *t) {
    LinkString *p = s->next, *q = t->next;
    while (p != NULL && q != NULL) {
        if (p != NULL && q != NULL)
            return 0;
        p = p->next;
        q = q->next;
    }
    if (p != NULL || q != NULL)
        return 0;
    else
        return 1;
}

LinkString *Concat(LinkString *s, LinkString *t) {
    LinkString *p = s->next, *q, *tc, *r;
    r = (LinkString *)malloc(sizeof(LinkString));
    tc = r;
    while (p != NULL) {
        q = (LinkString *)malloc(sizeof(LinkString));
        q->data = p->data;
        tc->next = q;
        tc = q;
        p = p->next;
    }
    p = t->next;
    while (p != NULL) {
        q = (LinkString *)malloc(sizeof(LinkString));
        q->data = p->data;
        tc->next = q;
        tc = q;
        p = p->next;
    }
    tc->next == NULL;
    return r;
}

LinkString *SubStr(LinkString *s, int i, int j) {
    int k = 1;
    LinkString *r, *p = s->next, *q, *tc;
    r = (LinkString *)malloc(sizeof(LinkString));
    r->next = NULL;
    if (i < 1)
        return r;
    tc = r;
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    if (p == NULL)
        return r;
    k = 1;
    q = p;
    while (k < j && q != NULL) {
        q = q->next;
        k++;
    }
    if (q == NULL)
        return r;
    k = 1;
    while (k <= j && p != NULL) {
        q = (LinkString *)malloc(sizeof(LinkString));
        q->data = p->data;
        tc->next = q;
        tc = q;
        p = p->next;
        k++;
    }
    tc->next = NULL;
    return r;
}

int Index(LinkString *s, LinkString *t) {
    LinkString *p = s->next, *p1, *q, *q1;
    int i = 1;
    while (p != NULL) {
        q = t->next;
        if (p->data == q->data) {
            p1 = p->next;
            q1 = q->next;
            while (p1 != NULL && q1 != NULL && p1->data == q1->data) {
                p1 = p1->next;
                q1 = q1->next;
            }
            if (q1 == NULL)
                return i;
        }
        p = p->next;
        i++;
    }
    return 0;
}

int InsStr(LinkString *&s, int i, LinkString *t) {
    LinkString *p = s, *q, *r;
    int k = 1;
    if (i < 1)
        return 0;
    while (k < i && p != NULL) {
        k++;
        p = p->next;
    }
    if (p == NULL)
        return 0;
    q = t->next;
    while (q != NULL) {
        r = (LinkString *)malloc(sizeof(LinkString));
        r->data = q->data;
        r->next = p->next;
        p->next = r;
        p = p->next;
        q = q->next;
    }
    return 1;
}

int DelStr(LinkString *&s, int i, int j) {
    LinkString *p = s, *q;
    int k = 1;
    if (i < 1 || j < 1)
        return 0;
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    if (p == NULL)
        return 0;
    k = 1;
    q = p->next;
    while (k <= j && q != NULL) {
        q = q->next;
        k++;
    }
    if (q == NULL)
        return 0;
    k = 1;
    while (k <= j) {
        q = p->next;
        if (q->next == NULL) {
            free(q);
            p->next = NULL;
        } else {
            p->next = q->next;
            free(q);
        }
        k++;
    }
    return 1;
}

LinkString *RepStrAll(LinkString *s, LinkString *s1, LinkString *s2) {
    int i;
    i = Index(s, s1);
    while (i > 0) {
        DelStr(s, i, StrLength(s1));
        InsStr(s, i, s2);
        i = Index(s, s1);
    }
    return s;
}

void DispStr(LinkString *s) {
    LinkString *p = s->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

//int Count(LinkString *s, LinkString *t) {
//    int num = 0, i = 0, m, n;
//    LinkString *p = s->next, *tc = p;
//    LinkString *q = t->next;
//    tc->next = p->next;
//    m = StrLength(s);
//    n = StrLength(t);
//    while (p->data == q->data) {
//        p = p->next;
//        q = q->next;
//        i++;
//
//        if (i == n) {
//            num++;
//            for (p = s; i < (num * (n - 1)); i++)
//                p = p->next;
//            i = 0;
//        }
//    }
//    if (p->data != q->data) {
//        p = tc->next;
//        tc = p;
//    }
//
//
//    return num;
//}

int Count(LinkString *s, LinkString *t) {
    int num = 0, i = 0, m, n;
    LinkString *p = s->next, *tc;
    LinkString *q = t->next;
    m = StrLength(s);
    n = StrLength(t);
    tc = p;
    while (i <= m - n)
//    while (tc != NULL)
    {
        while ( p->data == q->data) {
            p = p->next;
            q = q->next;
            i++;

            if (i == n) {
                num++;
                for (p = s->next; i < (num * (n - 1)); i++)
                    p = p->next;
                i = 0;
            }
        }
        if (p->data != q->data) {
            p = tc->next;
            tc = p;
        }
    }
    return num;
}

int main() {
    LinkString *s, *t;
    Assign(s, "abcdcdce");
    printf("s:");
    DispStr(s);
    Assign(t, "cd");
    printf("t:");
    DispStr(t);
    printf("重复字串个数：", Count(s, t));
    return 1;
    DestroyStr(s);
    DestroyStr(t);
}

以上是我的代码，期望解答。

Answer 1

重复字符不计算，直接跳过找到的串，然后从后面开始找子串。