题解 | #月月查华华的手机#

题意：

依次判断n个字符串是否是给定字符串的子串（不连续）

做法：

暴力做法

使用两个指针，分别从0开始比对，依次比对可能相等的字符。

但是遍历时间过长，需要加快遍历速度。

AC做法

仍然需要使用两个指针，可以考虑构造一个数组以加快父串指针的遍历速度。

可以构造一个整型数组pos[1000005][26]，26依次表示26个字母

其中：pos[i][0]表示在第i个字符后，最近的字符'a'的位置；其后没有字符'a'则为-1

#include<bits/stdc++.h>
using namespace std;

void solution(){
	// 存储华华的昵称中每一个字符后面第一个指定字符的位置
	// pos[i][0]表示第i个字符后，第一个出现字符'a'的位置 
	int pos[1000005][26];
	
	char name[1000005];
	scanf("%s", name); // 华华的昵称 
	
	// last[0]存储当前位置后第一个出现字符'a'的位置 
	int last[26];
	 
	// 初始化数组 
	memset(last, -1, sizeof(last));
	memset(pos, -1, sizeof(pos));
	
	// 构造pos数组 
	for(int i = strlen(name) - 1; i >= 0; i--){
		for(int j = 0; j < 26; j++){
			if(last[j] != -1){
				pos[i][j] = last[j];
			}
		}
		last[name[i] - 'a'] = i;
	}
	
	int n, i, j;
	scanf("%d", &n);
	char person[1000005]; // 可能被搭讪的人 
	bool ans; // 结果 
	for(int a = 0; a < n; a++){
		// 对n个朋友依次检查 
		scanf("%s", person);
		i = 0;
		j = 0;	
		while(name[i] == person[j]){
			i ++;
			j ++;
		}
		ans = true;
		while(j < strlen(person)){
			if(pos[i][person[j] - 'a'] != -1){
				i = pos[i][person[j] - 'a'];
				j ++;
			}else{
				ans = false;
				break;
			}
		}
		printf(ans ? "Yes\n" : "No\n");
	}
}

int main(){
	int test = 1;
	// cin >> test;
	while(test--){
		solution();
	}
	return 0;
}