牛客练习赛70 B.拼凑 (序列自动机)

题意:有一个模板串,有\(T\)个字符串,从字符串中找到某个子串,使得这个子串中的子序列包含模板串,求最短的子串的长度.
题解:找子序列,很容易想到序列自动机,根据序列自动机的原理,我们一定可以确保除了第一个字符,其他的字符的位置都是最优的,所以我们先对模板串的第一个字符\(p\)记录它的所有位置,然后再遍历它的位置,每次都跑一下序列自动机维护答案的最小值即可.

代码:

const string p="puleyaknoi";

int t;

string s;

vector<int> v[N];

vector<int> cnt;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

    	cin>>s;

    	cnt.clear();

    	int len=(int)s.size();

    	for(int i=0;i<len;++i){

    		int num=s[i]-'0';

    		v[num].pb(i);

    	}

    	for(int i=0;i<len;++i){

    		if(s[i]=='p') cnt.pb(i);

    	}

    	bool flag=false;

    	int res=INF;

    	for(auto w:cnt){

    		int pos=w;

    		for(int i=1;i<10;++i){

    			int num=p[i]-'0';

    			auto now=lower_bound(v[num].begin(),v[num].end(),pos+1);

    			if(now==v[num].end()){

    				break;

    			}

    			else pos=*now;

    			if(i==9){

    				flag=true;

    				res=min(res,pos-w+1);

    			}

    		}

    	}

    	if(!flag) cout<<-1<<endl;

    	else cout<<res<<endl;

    	for(auto w:s){

    		int num=w-'0';

    		v[num].clear();

    	}

    }

    return 0;

}

巴特西

牛客练习赛70 B.拼凑 (序列自动机)

最新文章

热门文章