Maximum Winter-Contest 2011 A: Shopping

keyword

尺取り法　C++

問題概要

長さM(<5*10^4)の文字列MとN(<=8)個の文字が与えられる。Nの文字が全て出現するような区間の最小幅を求める問題。

解法

蟻本に載ってる尺取り法の例題とほとんど同じ。なので詳細は蟻本参照のこと。

const int MAX_M = 52009;

int N, M;
int cnts[0x100];
bool ch[0x100];
char wants[20];
char prods[MAX_M];

int solve(){
    int ans = M;
    int s=0,t=0,cnt=0;
    for(int i=0; i<0x100; i++) ch[i] = false;
    for(int i=0; wants[i]; i++) ch[wants[i]] = true;
    for(int i=0; i<0x100; i++) cnts[i] = 0;
    while(1){
        while(t<M && cnt<N){
            if(ch[prods[t]] && cnts[prods[t]]++ == 0){
                cnt++;
            }
            t++;
        }
        if(cnt < N) break;
        ans = min(ans, t - s);
        if(ch[prods[s]] && --cnts[prods[s]] == 0){
            cnt--;
        }
        s++;
    }
    return ans;
}

int main(){
    while(scanf("%d%d ",&N,&M)){
        if(!N && !M) break;
        scanf("%s ",wants);
        scanf("%s ",prods);
        printf("%d\n",solve());
    }
    return 0;
}