MT3023 歌词中找单词-阿里云开发者社区

MT3023 歌词中找单词

2024-05-24 46

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： MT3023 歌词中找单词

1.暴力 10/12

#include <bits/stdc++.h>
using namespace std;
int n;
string a[10005];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    string ll;
    cin >> ll;
    for (int i = 0; i < n; i++)
    {
        string u = a[i];
        int num = 0;
        int j = 0;
        for (int k = 0; k < ll.size(); k++)
        {
            if (ll[k] == a[i][j])
            {
                num++;
                j++;
            }
        }
        if (num == a[i].size())
        {
            cout << "YES" << endl;
        }
        else
            cout << "NO" << endl;
    }
}

2.记录每个字母（共26个）的位置下标，并分别存在各自的字母下标数组中（例：a数组:1 3 5;b数组:2 6）

找一个字母的位置，即在此字母的下标数组中找（靠近左边的）&&（>前一个字母下标的数字）

(即若单词为bab，则先找b数组中最左侧位置2，再找a数组中>2&&最左侧的数字3，再找b数组中>3&&最左侧的数字6。如果都能找到位置，则说明此单词在歌词中)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, l, r, mid, ans;
string a[N], ll;
vector<int> abc[27]; // 字母下标数组
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    string ll;
    cin >> ll;
    for (int i = 0; i < ll.size(); i++)
        abc[ll[i] - 'a'].push_back(i); // 在各字母表中记录位置下标
    for (int i = 1; i <= n; i++)
    {
        int len = a[i].size(), now = -1; // now记录此时字母的位置应在now右侧
        int flag = 1;
        for (int j = 0; j < len; j++)
        {
 
            l = 0, r = abc[a[i][j] - 'a'].size() - 1, ans = -1; // 二分字母下标数组。找字母下标
            while (l <= r)
            {
                mid = (l + r) / 2;
                if (abc[a[i][j] - 'a'][mid] > now)
                {
                    r = mid - 1, ans = mid;
                }
                else
                    l = mid + 1;
            }
            if (ans == -1)//不能找到一个位置使此单词的某一字母在歌词中
            {
                flag = 0;
                break;
            }
            now = abc[a[i][j] - 'a'][ans];//now更新为此字母当前位置，下一字母的位置应在now之后
        }
 
        if (flag)
        {
            cout << "YES" << endl;
        }
        else
            cout << "NO" << endl;
    }
}