| 题目名称 | 1610. 子序列 |
|---|---|
| 输入输出 | subsequence.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 14 |
| 题目来源 |
 cqw
于2014-04-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：30， 提交：74， 通过率：40.54% | ||||
 AntiLeaf |
100 | 0.002 s | 0.12 MiB | C++ |
|
AntiLeaf |
100 | 0.005 s | 0.06 MiB | C++ |
 Metatron |
100 | 0.017 s | 7.39 MiB | C++ |
 Hzoi_ |
100 | 0.025 s | 0.40 MiB | C++ |
 King |
100 | 0.027 s | 23.56 MiB | C++ |
 LuciFer_T-J |
100 | 0.030 s | 10.33 MiB | C++ |
|
AntiLeaf |
100 | 0.033 s | 0.40 MiB | C++ |
 digital-T |
100 | 0.048 s | 0.32 MiB | C++ |
 超级傲娇的AC酱 |
100 | 0.057 s | 0.31 MiB | C++ |
 ww944606393 |
100 | 0.059 s | 0.31 MiB | C++ |
| 本题关联比赛 | |||
| 20140425 | |||
| 防止浮躁的小练习v0.7 | |||
| 关于 子序列 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
作死的静态指针池过不去TAT
我只好伸出自己罪恶的爪子，文件大小85.9kb | ||||
|
回复 @槿柒 :
谢谢 Metatron
2016-11-02 19:19
5楼
| ||||
|
膜拜楼上，好手速。。。
 槿柒
2016-11-02 19:19
4楼
| ||||
|
用gets读入会狗掉。。。
LuciFer_T-J
2014-04-28 20:12
3楼
| ||||
|
我为什么要建字典树呢……
| ||||
|
一种类似离散化的思想，避免遍历对结果没有贡献的信息。
可以二分优化。 | ||||
cstdio【题目描述】
如果存在一个数列C满足下列条件，我们就认为字符串A为字符串B的一个子序列：
(1)数列C恰好有length(A)个数；
(2)0<=C[0]<C[1]<...<C[length(A)-1]<length(B)；
(3)对于每一个i,有A[i]=B[C[i]]（0<=i<length(A)）。
举个例子，"abcd"是"aaaaaabbbcd"的子序列，而"abcd"不是"aaaaacccdb"的子序列，当然了，任意一个字符串都是它本身的一个子序列。
在本题中，给你一个较长的字符串A，和许多较短的字符串Bi，你需要写一个效率比较高的程序告诉我们Bi是否为A的子序列。
【输入格式】
输入文件的第一行为字符串A，第二行有一个整数M(0<M<=10000)，表示短字符串Bi的个数，接下来有M行，每行有一个字符串Bi。
字符串A的长度不超过100000，Bi的长度不超过50，所有的字符串都至少有一个字母，所有的字母均为小写。
【输出格式】
输出有M行，每行含义为：对于每一个Bi，如果它是A的子序列则输出"Yes"，否则输出"No"。
【样例输入】
subsequence 2 sequence bus
【样例输出】
Yes No