大二算法期末复习-习题-字符串计数

字符串计数

Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)

Statistic

Problem Description

给出m个字符串，要求输出重复n次的字符串有几个。

Input

先给定一个N，N≤100000，接着输入N个字符串。

Output

对于每组测试数据，输出若干行，每行两个正整数，第一个数表示重复的次数，第二个数表示在此重复次数下有几种不同的字符串。

Sample Input

5
BBA
BBA
BEA
DEC
CCF

Sample Output

CASE 1：
1 3
2 1

读取输入后，使用qsort函数进行排序，然后对连续出现的字符串进行计数，样例输出中 "CASE 1：" 是无用输出，直接输出就好。注："CASE 1：" 中的冒号应该为英文冒号，原文给的是中文冒号。

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

struct ch{
    char data[100];
};

int cmp(const void *a,const void *b){
    ch *p1 = (ch *)a;
    ch *p2 = (ch *)b;
    return strcmp(p1->data,p2->data);
}

ch in[100005];
int ans[100005];
int main()
{
	int t;
	cin>>t;
	for(int i = 0;i < t;i++){
        cin>>in[i].data;
	}
	qsort(in,t,sizeof(in[0]),cmp);
	memset(ans,0,sizeof(ans));
	int cf = 1;
	for(int i = 0;i < t;i++){
        if(strcmp(in[i].data,in[i+1].data)==0)
            cf++;
        else{
            ans[cf]++;
            cf = 1;
        }
	}
	cout<<"CASE 1:"<<endl;
	for(int i = 0;i <= t;i++){
        if(ans[i]!=0)
            cout<<i<<" "<<ans[i]<<endl;
	}
    return 0;
}