首页 > 试题广场 >

月月查华华的手机

[编程题]月月查华华的手机
  • 热度指数：1498 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！

输入描述:
第一行输入一个字符串A表示华华的昵称。
第二行输入一个正整数N表示华华的推荐好友的个数。
接下来N行，每行输入一个字符串B_i表示某个推荐好友的昵称。
，1\le N\le 2 \times 10^5，


输出描述:
输出N行，对于第i个推荐好友，如果华华可能向她搭讪，输出Yes，否则输出No。
注意大写，同时也要注意输出效率对算法效率的影响。
示例1

输入

noiauwfaurainairtqltqlmomomo
8
rain
air
tql
ntt
xiaobai
oiiiooo
orzcnzcnznb
ooooo

输出

Yes
Yes
Yes
Yes
No
Yes
No
No

备注:
本题已于下方时间节点更新，请注意题解时效性：
1. 2025-12-15 n 的数据范围从 10^6 缩减至 2 \times 10^5，同时增加了若干组数据。
算法知识视频讲解
添加回答
C++
Reisentyan头像 Reisentyan
我们将使用拉马努金瞪眼法解决这一题
注意到，这题不用AC自动机，不要把子序列看成子串
对于huahua的姓名来说，维护一个dp数组,
表示对于姓名的第 i 个字符，其下一个 j 字符在什么地方，j 为 0 到 25，对应 a 到 z
比如 abcda，对于字符 a 来说，下一个字符 b 在 2，下一个字符 c 在 3，下一个字符 a 在 5
然后对题目给的每一个字符串，进行一次匹配，比如 abc
从 a 开始，找下一个 b 在哪，找到 b 的位置了，找下一个 c 在哪，就这样匹配过去
注意到，代码要写成这样： 
void solve()
{
	string huahua; int n;
	cin >> huahua;
	n = q_;
	vector<vector<int>>dp(26, vector<int>(huahua.size()+1, -1));
	for (int i = huahua.size() - 1; i >= 0; i--)//位置i的下一个字母j在哪
	{
		int p = huahua[i] - 'a';
		for (int j = 0; j < 26; j++)
		{
			dp[j][i] = dp[j][i+1];
		}
		dp[p][i] = i+1;
	}
	ffp(i, 1, n)
	{
		string temp;
		bool flag = 1;
		cin >> temp;
		int now = 0;
		for (auto e : temp)
		{
			now = dp[e - 'a'][now];
			if (now == -1) { flag = 0; break; }
		}
		cout << (flag ? "Yes" : "No") << '\n';
	}
}

int main()
{
	int t = 1;
	while (t--)
	{
		solve();
	}

	return 0;
}


/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/



发表于 2025-12-15 00:52:16 回复(1)
C++
Estrella_pi头像 Estrella_pi

不是题解！
数据有点弱，随便写了一发暴力查找的代码，时间复杂度为O(N * q),最大能达到10^12，结果直接过了......
这么多正解，贴一下本蒟蒻写的暴力吧。

#include <iostream>
#include <string>

using namespace std;

string s, t;

void solve() {
    cin >> t;
    int l = 0;
    for(char ch : s) {
        if(ch == t[l]) l++;
        if(l >= t.size()) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

int main() {
    cin >> s;
    int q; cin >> q;
    while(q--) {
        solve();
    }

    return 0;
}
发表于 2025-12-15 14:47:10 回复(3)
Xuan2333头像 Xuan2333
通过nex数组表示下一个字母是啥，从而降低搜索时消耗的时间 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
char s[maxn];
int nex[maxn][26];
int main()
{
    scanf("%s", s + 1);
    int l = strlen(s + 1);
    for (int i = l - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            nex[i][j] = nex[i + 1][j];
        }
        nex[i][s[i + 1] - 'a'] = i + 1;
    }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s + 1);
        l = strlen(s + 1);
        int k = 0, ok = 0;
        for (int i = 1; i <= l; i++)
        {
            if (nex[k][s[i] - 'a'])
            {
                k = nex[k][s[i] - 'a'];
            }
            else
            {
                ok = 1;
                break;
            }
        }
        cout << (ok ? "No" : "Yes") << endl;
    }
    return 0;
}


发表于 2025-12-16 14:28:44 回复(0)
patrick_star1头像 patrick_star1
我不理解啊
有没有大佬帮忙看看啊 
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;
void judge(string user,deque<char> id);
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string yue,temp;
    cin>>yue;
    long long n;
    cin>>n;
    for (long long i=0;i<n;i++)
    {
        cin>>temp;
        deque<char> id(temp.begin(),temp.end());
        //copy_n(temp.begin(),temp.size(),back_inserter(id));
        judge(yue,id);
        id.clear();
    }
    return 0;
}
void judge(string user,deque<char> id)
{
    char *front,*back;
    front=&user[0];
    back=&user[user.size()-1];
    while (back-front>=0)
    {
        //cout<<*front<<' '<<*back<<endl;
        //cout<<back-front<<endl;
        if (*front!=id.front())
            front++;
        else
        {
            id.pop_front();
            front++;
        }
        if (id.empty())
        {
            cout<<"Yes\n";
            return;
        }
        if (*back!=id.back())
            back--;
        else
        {
            id.pop_back();
            back--;
        }
        if (id.empty())
        {
            cout<<"Yes\n";
            return;
        }
    }
    if (!id.empty())
        cout<<"No\n";
}


发表于 2025-12-16 12:27:39 回复(0)
Java
牛客203596504号头像 牛客203596504号
这道题是不是下午加了用例啊？上午AC的下午TLE了
发表于 2025-12-15 22:52:03 回复(0)
C++
mollor头像 mollor
时间复杂度没看出来，我这个为什么能过啊？神秘find 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;

void solve()
{	
    string a;
    cin>>a;
    int n;
    cin>>n;
    while (n--)
    {
        string s;
        cin>>s;
        int cur = 0;
        bool fl = 0;
        for (int i = 0 ; i < s.size() ; i++)
        {
            int tt = a.find(s[i],cur);
            if (tt == -1)
            {
                cout<<"No\n";
                fl = 1;
                break;
            }
            cur = tt + 1;
        }
        if (fl) continue;
        cout<<"Yes\n";
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}


发表于 2025-12-15 19:34:04 回复(0)
提交观点

问题信息

思维题
难度：
6条回答 125浏览

热门推荐

相关试题

月月查华华的手机

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号