总时间限制:1000ms 内存限制: 65536kB
描述
给出一个只包含0和1的字符串(长度在1到100之间),求其每一个子串出现的次数。
输入
一行,一个01字符串。
输出
对所有出现次数在1次以上的子串,输出该子串及出现次数,中间用单个空格隔开。按子串的字典序从小到大依次输出,每行一个。
样例输入
10101
样例输出
0 2
01 2
1 3
10 2
101 2
ac代码
/*
@File : substring_calculation.cpp
@Time : 2020/03/23
@Desc : 子串计算
*/
#include <iostream>
#include <stdlib.h>
#include <string>
#include <cmath>
using namespace std;
//子串结点
typedef struct Node
{
string str; //子串
int count; //出现次数
struct Node *next; //下一个子串
} *sstring;
/**
* @brief 初始化node
*
* @param node 需要初始化的node
*/
void initNode(sstring &node);
/**
* @brief 判断子串A字典序是否小于B的字典序
*
* @param A 子串A
* @param B 子串B
* @return true
* @return false
*/
bool judge(const sstring A, const sstring B);
/**
* @brief 删除sub中属性为count的子串
*
* @param count 属性count
* @param sub 子串列
*/
void delete_element_count_is(int count,sstring &sub);
/**
* @brief 插入子串
*
* @param node 子串
* @param substring 子串列
*/
void insert(sstring node, sstring &substring);
/**
* @brief 输出子串列包含信息
*
* @param substring 子串列
*/
void print_substring(const sstring substring);
/**
* @brief Get the substring object
*
* @param str 母串
* @return sstring 母串所有子串
*/
sstring get_substring(const string str);
int main(int argc, char const *argv[])
{
string str;
cin >> str;
print_substring(get_substring(str));
system("pause");
return 0;
}
void initNode(sstring &node)
{
//node =(sstring)malloc(sizeof(Node));//不用malloc分配,结构体包含string类,无法初始化
node = new Node(); //new初始化正确
node->count = 1;
node->next = NULL;
}
bool judge(const sstring A, const sstring B)
{
int len;
if(A->str.size()!=B->str.size()) {
len = min(A->str.size(),B->str.size());
for (int i = 0; i < len; i++) {
if (A->str[i] == '0'&&B->str[i] == '1') return true;
if (A->str[i] == '1'&&B->str[i] == '0') return false;
}
if (A->str.size()>B->str.size()) return false;
else return true;
} else {
len = A->str.size();
for (int i = 0; i < len; i++) {
if (A->str[i] == '0'&&B->str[i] == '1') return true;
if (A->str[i] == '1'&&B->str[i] == '0') return false;
}
return false;
}
}
void delete_element_count_is(int count,sstring &sub)
{
/**
* 在构建的有序(字典序升)子串列中
* 删除出现次数为count的子串
*/
for (sstring n = sub;n->next;)
{
if (n->next->count==count) {
n->next=n->next->next;
} else {
n = n->next;
}
}
}
void insert(sstring node, sstring &substring)
{ sstring n, this_node;
for (this_node = substring; this_node->next; this_node = this_node->next) {
if (judge(node,this_node->next)){
initNode(n);
n->str = node->str;
n->next = this_node->next;
this_node->next = n;
return;
}
if (node->str==this_node->next->str) {
this_node->next->count++;
return;
}
}
initNode(n);
n->str = node->str;
n->next = this_node->next;
this_node->next = n;
}
void print_substring(const sstring substring)
{
for (sstring n = substring->next; n; n = n->next) {
cout<< n->str << " " << n->count << endl;
}
}
sstring get_substring(const string str)
{
sstring substring, head, node;
initNode(substring);
head = substring;
for (int i = 0; i < str.size(); i++) {
initNode(node);
for (int j = i; j < str.size(); j++) {
node->str = node->str + str[j];
insert(node,substring);
}
}
delete_element_count_is(1,substring);
return substring;
}
}
c```