【思路】月月查华华的手机

题目：牛客网 NC23053 月月查华华的手机

题目的大意是，给一个字符串A，以及N个字符串Bi，对于每一个Bi，询问其是否A的子序列。

错误1：混淆子序列和子串

本蒟蒻刚复习KMP，看到这道题就想套，却连样例都过不了，后来发现问的是子序列而不是子串。

子序列和子串的最大区别是，子串一定要连续的，而子序列可以不连续。例如，字符串"aeaijgoaeljo"，它的子序列可以是"aea"，也可以是"aio"；但是"aio"不是它的子串。

思路1：暴力求解

对于每一个Bi，都遍历一次A寻找Bi中的每一个字母。用a维护在字符串A中遍历到的位置，用b维护在字符串Bi中正在寻找的位置。

例如，A="noiauw"    B1="oaw"

刚开始，a=0（指向n），b=0（指向o）。

然后保存b不动，a一直++，直到找到A中的第一个字母"o"为止，这时b就要++，表示要在A中寻找B的下一个字母的位置了

一直以此类推，直到Bi的最后一个字母都在A中找到了，就表示匹配成功，输出Yes；或者A已经遍历完了，但还没有找到Bi的所有字母，表示匹配失败，输出No

改进：记录26个字母第一次在A中出现的位置

用数组position[30]记录26个字母第一次在A中出现的位置，这样就省去了找Bi第一个字母的时间了。

还是上面的例子，B1的第一个字母是"o"，查表发现"o"第一次在A中出现的位置是下标1，所以a,b的初始化如下

 代码如下：

#include
using namespace std;
 
char A[1000000];
int position[30];//A中各个字母首次出现的位置
 
int find(char*B)
{
    int alen=strlen(A);
    int blen=strlen(B);
    int a=position[B[0]-'a'];
    int b=0;
    if(a==-1) return 0;
    else
    {
        for(int i=a;i

错误2：用cin cout容易超时

我把改进思路编成代码提交，却超时了。我看答案有人用暴力思路都能过，就怀疑是cin cout的锅，然后把所有的cin cout改成scanf printf之后，就过了。

思路2：优化枚举

其实我觉得暴力求解的话，如果数据量很大会过不了

后来看题解，发现了一种很有趣的思路，大大减少了时间复杂度。

这种思路是在我的改进思路之上优化的。既然已经记录下每一个字母第一次在A中出现的位置，那么就同样可以记录下从A中的第i个位置开始各个字母第一次在A中出现的位置。

还是以"noiaw"举例，i=0时，跟position数组一样，就是26个字母在A中第一次出现的位置

i=1时，可以看作是26个字母在字符串"0oiauw"中第一次出现的位置

以此类推

这样子就不用遍历A了，只需要遍历Bi即可

比如B1="oaw"，初始位置如下

查表得A中第0位开始的第一个"o"在位置1

A中第1位开始的第一个"a"在位置3

A中第3位开始的第一个"w"在位置5

此时B已经遍历完成，输出"Yes"；假如在这个过程中得到数字-1，就可以输出"No"了，大大降低了时间复杂度。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/3002911.html