月月查华华的手机 题解
月月查华华的手机
https://ac.nowcoder.com/acm/problem/23053
很简单的一道枚举优化题(java代码)，只需要简单优化即可通过。
因为复杂度过大的话会导致超时，所以我们要对这个程序加以优化。
首先创一个num[i][k]数组i代表26个字符，k用来记录每一个i字符在s当中的位置，以便后面查找对比使用。
next数组用来记录每一个s中有多少个此字符，也方便存放i的位置了。
这里注意，我们可以先判断s1首个字符在s中是否存在也就是说next数组对应的是否为0，如果为0的话就代表不存在也就没必要比对了直接输出No，也算是一个小优化吧。
之后再遍历输入的s1，如果i-1字符的位置在i字符位置之后就可以构成子序列了。如果全部都是在前一个字符之后，就可以输出Yes。
所以我们只需要创一个nexts数组来存放s1中此字符的位置。
然后遍历即可，代码可能有些啰嗦，原谅我刚开始学习不太会精简的代码，欢迎指正。
代码如下java。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
String s = in.sval;
in.nextToken();
int n = (int)in.nval;
int next[] = new int[26];
int nexts[] = new int[26];
int num[][] = new int[26][1000000];
for(int i=0;i<s.length();i++)
{
num[s.charAt(i)-'a'][next[s.charAt(i)-'a']] = i;
next[s.charAt(i)-'a']++;
}
boolean dui = true;
int q=0;
for(int t=0;t<n;t++)
{
dui = true;
in.nextToken();
String s1 = in.sval;
Arrays.fill(nexts,0);
if(next[s1.charAt(0)-'a']!=0)
{
q = num[s1.charAt(0)-'a'][0];
nexts[s1.charAt(0)-'a']++;
for(int i=1;i<s1.length();i++)
{
while(num[s1.charAt(i)-'a'][nexts[s1.charAt(i)-'a']]<q&&nexts[s1.charAt(i)-'a']<=next[s1.charAt(i)-'a'])
{
nexts[s1.charAt(i)-'a']++;
}
if(num[s1.charAt(i)-'a'][nexts[s1.charAt(i)-'a']]<q)
{
dui = false;
break;
}
else{
q = num[s1.charAt(i)-'a'][nexts[s1.charAt(i)-'a']];
nexts[s1.charAt(i)-'a']++;
}
}
if(dui==true)
out.println("Yes");
else{
out.println("No");
}
}
else{
out.println("No");
}
}
out.flush();
}
} 