【洛谷 P1628】合并序列 题解（字符串+映射）

合并序列

题目描述

有 $N$ 个单词和字符串 $T$，按字典序输出以字符串 $T$ 为前缀的所有单词。

输入格式

输入文件第一行包含一个正整数 $N$；

接下来 $N$ 行，每行一个单词，长度不超过 $100$；

最后一行包含字符串 $T$。

输出格式

按字典序升序输出答案。

样例 #1

样例输入 #1

6
na
no
ki
ki
ka
ku
k

样例输出 #1

ka
ki
ki
ku

提示

【数据规模】

对于 $60\%$ 的数据，满足 $1\le N\le 1000$；

对于 $100\%$ 的数据，满足 $1\le N\le 100000$ 且所有字符均为小写字母。

思路

用一个 while 循环读入 n 行字符串，将每个字符串作为 map 的 key，将其出现次数作为 value 存入 map 中。

遍历 map 中的每个元素，如果该元素的 key 以 t 开头，则输出该 key 对应的字符串 i.first，输出次数为 i.second 次。文章来源地址https://uudwc.com/A/jry6e

AC代码

#include <iostream>
#include <map>
#define AUTHOR "HEX9CF"
using namespace std;

int main()
{
    int n;
    string t;
    map<string, int> m;
    cin >> n;
    while (n--)
    {
        string in;
        cin >> in;
        m[in]++;
    }
    cin >> t;
    for (const auto &i : m)
    {
        int index = i.first.find(t);
        if (!index)
        {
            for (int j = 0; j < i.second; j++)
            {
                cout << i.first << endl;
            }
        }
    }
    return 0;
}