子串计算

[编程题]子串计算

热度指数：9917 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给出一个01字符串（长度不超过100），求其每一个子串出现的次数。

输入描述:

输入包含多行，每行一个字符串。

输出描述:

对每个字符串，输出它所有出现次数在1次以上的子串和这个子串出现的次数，输出按字典序排序。

示例1

输入

输出

算法知识视频讲解

mabaoguo

思路可以是这样：

思路1⃣️.构建一个Map，按照Map的去重的性质，对Map中的不同的字符串string进行计数，然后直接按顺序打印Map的键值对即可。

思路2⃣️.字典树：由于子串只有0和1，因此可以构造一颗二叉树，二叉树的孩子节点向左为0，向右为1，然后双重循环，对二叉树进行遍历+构造，即一方面遍历节点，另一方面遇到NULL就新建节点，由此构造一颗节点总数不超过100的二叉树（遍历起来很快，二叉树的优点之一），然后通过前序遍历+回溯即可完成打印。

由于使用的是C语言，没有什么标准库可以直接用，所以有的方面限制还是很大的。

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

typedef struct TreeNode {
    int count;
    char val;                // 0-左 1-右
    struct TreeNode* left;   //左节点-0
    struct TreeNode* right;  //右节点-1
} TNode;

void printTree(char* t, TNode* root) {
    //前序遍历打印二叉树
    if (root) {
        if (root->count > 1) {  //输出t中的所有字符，并且打印本次遍历的字符
            printf("%s%c %d\n", t, root->val, root->count);
        }
        int length = 0;
        for (int i = 0; t[i] != '\0'; i++) {
            length++;
        }
        t[length] = root->val;
        printTree(t, root->left);
        printTree(t, root->right);
        t[length] = '\0';  //剪枝
    }
}

void getSubParam(char s[]) {
    //构建一颗二叉树，字典树
    TNode* initNode = (TNode*)malloc(sizeof(TNode));  //创世块
    int length = 0;
    while (s[length] != '\0') {
        length++;
    }
    for (int i = 0; i < length; i++) {
        TNode* tmp = initNode;
        for (int j = i; j < length; j++) {
            //双重循环
            if (s[j] == '0') {
                if (!tmp->left) {
                    //没有左孩子，手动申请一个空间放左孩子
                    tmp->left = (TNode*)malloc(sizeof(TNode));
                    tmp->left->val = '0';
                    tmp->left->count = 0;
                }
                tmp->left->count++;
                tmp = tmp->left;
            }
            if (s[j] == '1') {
                if (!tmp->right) {
                    tmp->right = (TNode*)malloc(sizeof(TNode));
                    tmp->right->val = '1';
                    tmp->right->count = 0;
                }
                tmp->right->count++;
                tmp = tmp->right;
            }
        }
    }
    char* tmp1 = (char*)malloc(sizeof(char) * 101);
    char* tmp2 = (char*)malloc(sizeof(char) * 101);
    printTree(tmp1, initNode->left);
    printTree(tmp2, initNode->right);
}

//字典二叉树
int main() {
    char s[100];
    // FILE* fp = fopen("./data.in", "r");
    while (scanf("%s\n", s) != EOF) {
        getSubParam(s);
    }
}

发表于 2022-03-19 15:35:45 回复(0)