模板题:https://nanti.jisuanke.com/t/38232

可以求出一个序列中是否存在某个子序列

基本思想

定义一个next数组,用来存储在第i位后面出现的序列中的某一个元素的出现位置。

例如字符串abcdefg[字符串下标从一开始]

可以得到next的内容为:

next[0]['a'] = 1;    next[1]['a'] = -1;   next[2]['a'] = -1;    ......
next[0]['b'] = 2;    next[1]['b'] = 2;    next[2]['b'] = -1;    ......
next[0]['c'] = 3;    next[1]['c'] = 3;    next[2]['c'] = 3;     ......
next[0]['d'] = 4;    next[1]['d'] = 4;    next[2]['d'] = 4;     ......
next[0]['e'] = 5;    next[1]['e'] = 5;    next[2]['e'] = 5;     ......
next[0]['f'] = 6;    next[1]['f'] = 6;    next[2]['f'] = 6;     ......
next[0]['g'] = 7;    next[1]['g'] = 7;    next[2]['g'] = 7;     ......

然后在查询其子序列是否存在时,只要找到子串第i个元素出现的位置[记做j],然后在next中查找j开始的子串中i+1个元素是否存在即可。

优化思想

在建立next数组时,可以从后往前遍历主串,并用last数组记录当前的i以后第一个出现的序列中的元素位置,并不停刷新到next就可以在O(n)下求出next。

[要空出next[0]来储存整串中数值最早出现的数的位置]

代码

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 100;
const int MAXC = 26;
int nxt[MAXN][MAXC];
int last[MAXC];
int main() {
	string T;
	T.resize(MAXN);
	scanf("%s", &T[0]);
	T = " " + T;
	memset(last, -1, sizeof last);
	int len = strlen(T.c_str());
	for(int i = len - 1; i >= 0; i--) {
		for(int j = 0; j < MAXC; j++)
			nxt[i][j] = last[j];
		if(i == 0) continue;
		last[T[i] - 'a'] = i;
	}
	int m;
	scanf("%d", &m);
	while(m--) {
		string temp;
		temp.resize(MAXN);
		scanf("%s", &temp[0]);
		int templen = strlen(temp.c_str());
		bool b = true;
		int tempn = 0;
		for(int i = 0; i < templen; i++) {
			tempn = nxt[tempn][temp[i] - 'a'];
			if(tempn == -1) {
				printf("NO\n");
				b = false;
				break;
			}
		}
		if(b) printf("YES\n");
	}
	return 0;
}

发表回复