NOIP 提高 2016 第一轮 第 24 题：贪心判断子序列（缩写匹配）

题目

```
#include <iostream> 
using namespace std;
int main()
{
    char a[100][100], b[100][100];
    string c[100];
    string tmp;
    int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
    cin >> n;
    getline(cin, tmp);
    for (i = 0; i < n; i++)
    {
        getline(cin, c[i]);
        total_len[i] = c[i].size();
    }
    for (i = 0; i < n; i++)
    {
        j = 0;
        while (c[i][j] != ':')
        {
            a[i][k] = c[i][j];
            k = k + 1;
            j++;
        }
        length[i][1] = k - 1;
        a[i][k] = 0;
        k = 0;
        for (j = j + 1; j < total_len[i]; j++)
        {
            b[i][k] = c[i][j];
            k = k + 1;
        }
        length[i][2] = k - 1;
        b[i][k] = 0;
        k = 0;
    }
    for (i = 0; i < n; i++)
    {
        if (length[i][1] >= length[i][2])
            cout << "NO,";
        else
        {
            k = 0;
            for (j = 0; j < length[i][2]; j++)
            {
                if (a[i][k] == b[i][j])
                    k = k + 1;
                if (k > length[i][1])
                    break;
            }
            if (j == length[i][2])
                cout << "NO,";
            else
                cout << "YES,";
        }
    }
    cout << endl;
    return 0;
}
```
输入：  
3  
AB:ACDEbFBkBD  
AR:ACDBrT  
SARS:Severe Atypical Respiratory Syndrome     
输出：_________
（注：输入各行前后均无空格）

请写出程序的输出结果。

答案

YES,NO,YES,

题解

考点定位

本题考「缩写匹配模拟」,对应大纲 4.2.1 模拟（难度【4】）。

解题过程

每组输入「缩写:全称」，判断缩写是否匹配全称（贪心子序列）。按原卷三组输入 AB:ACDEbFBkBD、AR:ACDBrT、SARS:SARS：

输出 YES,NO,YES,（按官方答案）。

易错提醒

① 匹配逻辑：全称长度必须大于缩写长度，否则 NO；② 逐字符贪心推进，走完缩写即 YES。