Codeforces 997B. Two-gram——————水题复习一下map

太过爱你忘了你带给我的痛 2022-04-05 08:14 111阅读 0赞

# B. Two-gram #

Two-gram is an ordered pair (i.e. string of length two) of capital Latin letters. For example, “AZ”, “AA”, “ZA” — three distinct two-grams.

You are given a string s consisting of n capital Latin letters. Your task is to find any two-gram contained in the given string as a substring (i.e. two consecutive characters of the string) maximal number of times. For example, for string s = “BBAABBBA” the answer is two-gram “BB”, which contained in s three times. In other words, find any most frequent two-gram.

Note that occurrences of the two-gram can overlap with each other.

### Input ###

The first line of the input contains integer number n (2≤n≤100) — the length of string s. The second line of the input contains the string s consisting of n capital Latin letters.

### Output ###

Print the only line containing exactly two capital Latin letters — any two-gram contained in the given string s as a substring (i.e. two consecutive characters of the string) maximal number of times.

### Examples ###

input  
7  
ABACABA  
output  
AB

input  
5  
ZZZAA  
output  
ZZ

### Note ###

In the first example “BA” is also valid answer.

In the second example the only two-gram “ZZ” can be printed because it contained in the string “ZZZAA” two times.

--------------------

这道题就是找给定字符串中的长度为2的连续子串出现的次数

str.substr(i,j) 从下标 i 开始，生成长度为 j 的子串  
遍历map的时候需要

map<string,int> ma;
    for(map<string,int>::iterator it = ma.begin(); it!=ma.end();++it)
    {
        
    	cout<<it->first;
    	cout<<" "<<it->second<<endl;
    }

--------------------

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	string str;
    	map<string,int> ma;
    	int len;
    	cin>>len>>str;
    	for(int i=0;i<len-1;++i)
    		ma[str.substr(i,2)]++;//str.substr(i,j)  从下标 i 开始，生成长度为 j 的子串 
    	string ans;
    	int x = 0;
    	for(map<string,int>::iterator it = ma.begin(); it!=ma.end();++it)
    	{
        
    		if(it->second>=x)
    		{
        
    			x = it->second;
    			ans = it->first;
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }