Statement

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

Idea

注意到字符集的种类非常的小, 只有26种. 因此我们就可以在此枚举: 比如记录下来每一个字符最后的出现位置. 存在head里面, 同样的也可以记录下每一个的下一个字符在哪里, 用nxt表示. 因此就可以较为快速的完成整个问题.

Code Sample

#define CTI(x) ((int)(x-'a')) // char to int
int nxt[MAXN][26], head[26];
string s;
void get{
	sz = s.size();
	//Enum pos
	Fd(i, sz-1, 0){
		//Enum char from A..Z(0..25)
		F(j, 0, 25){
			if(CTI(s[i]))==j){
				head[j]=i;
			}
		}
	}
}
bool fd(string t){
	int sz = t.length();
	F(i = head[CTI(s[0])]; ~i; i = nxt[i][CTI(s[0])]){
		bool flag = 1;
		F(j, 0, sz-1){
			nxt[i][j] = head[j]; // 每一个都是要求的
			if(t[j]!=s[i+j]) {
				flag = 0;
				break;
			}
		}
		if(flag) return 1; else return 0;
	}
}