AOJ1215 Co-occurrence Search - nanikakaのAOJ航海日誌

概要

文字列Sとk個の文字が与えられる。文字列Sの部分文字列の中で、k個の文字が全て現れるものの中で最短の長さとなる区間がいくつあるかを答えよ。そのような区間が1つ以上存在する場合、最も最初に現れた区間を答えよ。
Sの長さ <= 10^6
k <= 50

解法

Sの長さがキチガイなので下手な方法はとれません。今回は尺取り法で解きました。
2つの変数s, tを用意し、常にs<=tです。Sの中の[s, t]を部分文字列と考えます。部分文字列の長さはt-s+1となります。
初期値はs = 0, t = -1です（処理の都合でこの瞬間だけs<=tを満たしません）。
[s, t]の部分文字列中にk個のキーそれぞれが何個登場しているかを管理します。
今の部分文字列に1つも登場していないキーがある場合はtを1増やします。そしてその増えた分の文字がキーの場合、そのキーの個数を増やします。
全てのキーが含まれている場合、それは条件を満たす部分文字列になっています。解の更新を行います。そしてsを1増やします。このとき、削った1文字がキーの場合は、そのキーの個数を減らします。
この処理をtがSの範囲を飛び越えるまでやれば解けます。

ソース

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//Co-occurrence Search
public class AOJ1215 {

	void run(){
		Scanner sc = new Scanner(System.in);
		boolean head = true;
		while(sc.hasNext()){
			if(!head)sc.nextLine();
			StringBuilder sb = new StringBuilder();
			for(;;){
				String s = sc.nextLine();
				if("".equals(s))break;
				sb.append(s);
			}
			char[] ch = sb.toString().toCharArray();
			int n = ch.length;
			String key = sc.nextLine();
			int k = key.length();
			Map<Character, Integer> ref = new HashMap<Character, Integer>();
			for(int i=0;i<k;i++)ref.put(key.charAt(i), i);
			int[] c = new int[k];
			int kind = 0;
			int s = 0, t = -1;
			int res = 0, min = n+1;
			String ans = "";
			for(;;){
				if(kind==k){
					int len = t-s+1;
					if(len<min){
						min = len;
						res = 1;
						ans = sb.substring(s, t+1);
					}
					else if(len==min)res++;
					if(ref.containsKey(ch[s])){
						int x = ref.get(ch[s]);
						c[x]--;
						if(c[x]==0)kind--;
					}
					s++;
				}
				else{
					t++;
					if(t==n)break;
					if(ref.containsKey(ch[t])){
						int x = ref.get(ch[t]);
						if(c[x]==0)kind++;
						c[x]++;
					}
				}
			}
			System.out.println(res);
			if(res!=0){
				System.out.println();
				for(int i=0;i<ans.length();i+=72)System.out.println(ans.substring(i, Math.min(ans.length(), i+72)));
			}
			System.out.println();
			head = false;
		}
	}
	
	public static void main(String[] args) {
		new AOJ1215().run();
	}
}