[TIOJ] 1489. E.核心字串

題目連結:http://tioj.infor.org/problems/1489
經典(?的雙指針題,每次右界擴充的時候就判斷一下左界的那個字元是不是出現超過一次了,如果超過一次表示他其實不必要。此外透過計算每個字元出現的次數也可以計算是否26個字母都出現過了,作法大概就是發現這個字元出現了,且之前他沒出現過就讓某一個變數增加一。最後判一下該變數是否為26就好了。
#include <bits/stdc++.h>
using namespace std;

const int INF = 2000000;
const int N = 1000000 + 5;
char str[N];
int cnt[256], c=0;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		fill(cnt, cnt+256, 0);
		c=0;
		cin>>str;
		int ansL=0, ansR=INF;
		int curL=0, curR;
		for(curR=0;curR<n;curR++){
			if(cnt[(unsigned)str[curR]]==0) c++;
			cnt[(unsigned)str[curR]]++;
			while(cnt[(unsigned)str[curL]]>1){
				cnt[(unsigned)str[curL]]--;
				curL++;
			}
			if(c==26){
				if(ansR-ansL > curR-curL){
					ansR=curR;
					ansL=curL;
				}
			}
		}
		if(c<26){
			cout<<"not found\n";
		}else{
			for(int i=ansL;i<=ansR;++i)
				cout<<str[i];
			cout<<'\n';
		}
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology