C++子串计算

内存限制：64 MB时间限制：1.000 S

题目描述

给出一个只包含0和1的字符串（长度在1到100之间），求其每一个子串出现的次数。

输入

一行，一个01字符串。

输出

对所有出现次数在1次以上的子串，输出该子串及出现次数，中间用单个空格隔开。按子串的字典序从小到大依次输出，每行一个。

样例输入 复制

10101

样例输出 复制

0 2
01 2
1 3
10 2
101 2

题型：枚举

#include<bits/stdc++.h>
using namespace std;

int main(){
	string s;//建立一个string类型的的字符串
	cin>>s;//输入
	vector<string>a;//建立1个string类型的动态数组
	for(int i=0;i<s.size();i++){//枚举2个元素
		for(int j=1;j<=s.size()-i;j++){
			a.push_back(s.substr(i,j));//插入的同时提取子串
		}
	}
	sort(a.begin(),a.end());//给动态数组里的元素按照字典序排序
	a.erase(unique(a.begin(),a.end()),a.end());//用erase删除unique去重的结果
	for(int i=0;i<a.size();i++){//继续循环遍历
		int sum=0,xb=0;//定义整型的计数器和下标
		while(s.find(a[i],xb)<s.size()){//字符串a里寻找动态数组a[i]和下标
			sum++;//每循环一次sum自加
			xb=s.find(a[i],xb)+1;//将字符串中找到的a[i]和下标的值赋个给下标
		}
		if(sum>1){
			cout<<a[i]<<' '<<sum<<endl;
		}
	}
	return 0;
}