子串计算

[编程题]子串计算

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

狐尼克201907031526675

1、遍历得到所有字符串种类

2、去掉重复字符串

3、利用strcmp函数和排序算法得到各个字符的顺序

4、再利用得到的顺序将字符串按顺序排列进数组

5、将排列好的字符串数组按顺序依次判断出现次数，然后输出。

排序算法举例：例子5、3、4、2

将每一个数字与另外所有数字比较，大的那个数的标记index[i] 加一

计算下来他们的标记index[i]为：6、2、4、0

那这样就知道了他们的大小顺序

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX 1000

//计算字符串出现次数
int Findkey(char nstr[], char find[], int l1) {
    int key = 0, i, j;
    key = 0;
    int l2 = strlen(find);
    for ( i = 0; i <= l1 - l2; i++) {
        for ( j = 0; j < l2; j++) {
            if (nstr[j + i] != find[j]) break;
        }
        if (j == l2) key++;
    }
    return key;

}

int main() {
    char nstr[MAX],
         find[MAX][MAX]; //nstr:输入的字符串  find为遍历出来的所有字符串
    int key = 0, l1, l2, i, j, m, times = 0, k = 0, kstr = 0;
    scanf("%s", nstr);
    l1 = strlen(nstr);

//遍历所有字符串
    for ( i = 0; i < l1; i++) {
        for (m = 1; m <= l1 - i; m++) {
            k = 0;
            for (j = i; j < m + i; j++) {
                find[kstr][k] = nstr[j];
                k++;
            }
            times ++;
            kstr++;
        }
    }
    //去掉重复字符串
    for (i = 0; i < kstr; i++) {
        for (int j = i + 1; j < kstr; j++) {
            if (strcmp(find[i], find[j]) == 0) find[j][0] = '\0';
        }
    }

    char findend[MAX][MAX],
         findtmp[MAX][MAX]; // findend为最终去重和排序之后的字符串数组，findtemp为find去重之后的数组
    int index[MAX], timesend = 0;
    for (i = 0; i < times; i++) {//去掉空位。让字符串相邻排列，，因为前面去重后会出现空位
        if (find[i][0] != '\0') {
            strcpy(findtmp[timesend], find[i]);
            timesend ++;
        }
    }
    for ( i = 0; i < timesend; i++) {//排序，index[i]记录findtmp[i]里的字符串的排序大小
        for (j = 0; j < timesend; j++) {
            if (strcmp(findtmp[i], findtmp[j]) > 0) index[i]++;
            else if (strcmp(findtmp[i], findtmp[j]) < 0) index[j]++;

        }
    }
    int lengthend = 0;
    for (i = 0; i < timesend; i++) { // 根据index里的信息 将findtmp里的字符串按从小到大排序到findend中
        strcpy(findend[index[i]], findtmp[i]);
        if (index[i] > lengthend)  lengthend = index[i];
    }
    for (i = 0; i < lengthend; i++) {//把findend中的字符串送到Findkey中查找每一个字符串出现的次数 key 
        if (findend[i][0] != '\0') {
            key = Findkey(nstr, findend[i], l1);

            if (key > 1) {
                printf("%s %d\n", findend[i], key);
            }
        }
    }

    return 0;
}

发表于 2025-02-27 21:22:57 回复(0)

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)