首页 > ACM题库 > 九度OJ > 九度-1149-子串计算[解题代码]
2013
12-12

九度-1149-子串计算[解题代码]

题目来源:2010年北京大学计算机研究生机试真题

题目描述:

给出一个01字符串(长度不超过100),求其每一个子串出现的次数。

输入:

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

输出:

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

样例输入:
10101
样例输出:
0 2
01 2
1 3
10 2
101 2

cpp 代码如下:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char arr[5000][101];
int cmp(const void * a,const void *b){
	return strcmp((char*) a,(char *)b);
}
int main(){
	char str[101]= {'\0'};
	while(scanf("%s",str) != EOF){
		int n = strlen(str);
		int index = 0;
		memset(arr,'\0',sizeof(arr));
		for(int i=0; i<n; i++){
			for(int j=i; j<n; j++){
				int m = 0;
				char tmp[101]= {'\0'};
				for(int k=i; k<=j; k++){  // 得到子串tmp,再复制到arr中
					tmp[m++] = str[k];
				}
				strcpy(arr[index++],tmp);
			}
		}
		qsort(arr,index+1,sizeof(char[101]),cmp);
		for(int i=0; i<index; i++){
			int count = 1;
			while(strcmp(arr[i],arr[i+1]) == 0)
				count++,i++;
			if(count>1)
				printf("%s %d\n",arr[i],count);
		}
	}
	return 0;
}

/**************************************************************
	Problem: 1149
	User: coder
	Language: C
	Result: Accepted
	Time:10 ms
	Memory:1404 kb
****************************************************************/


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。