AOJ1291 Search of Concatenated Strings

AOJ Volume12

問題リンク Search of Concatenated Strings

  • 概要

N個の文字列Ei と文字列Sが与えられる。Eiの各要素を1回ずつ連結した文字列が現れる箇所はSの中にいくつあるか答えよ。Eiの連結する順番は任意でよい。例えば、Eiが"a"と"b"であれば、"ab"もしくは"ba"が探すべき文字列となる。
また、出現箇所の個数を数えるため、例えば
Ei: "x", "xx"
S: "xxx"
のとき、"x"+"xx"と"xx"+"x"の2種類が現れるが、種類は問わず、これは1回とカウントする。
連結文字列がオーバラップしている場合は位置がずれるので、複数回カウントする。
Ei: "x", "xx"
S: "xxxx"
の場合、前半の"xxx"部分と、後半の"xxx"部分にそれぞれ連結文字列が出現しているのでこれは2回とカウントする
1 <= N <= 12
1 <= |Ei| <= 20
1 <= |S| <= 5000

  • 解法

DPっぽく解きます。
e[ i ][ j ]: インデックスiを末尾にした文字列を考えたとき、そこに集合 j の文字列を作ることができる
という表を埋めて解きます。jの中のkビット目が1だった場合、Ekを使った連結文字列が作れるという意味です。
この表を先頭から埋めていき、j == 2^N - 1となっているインデックスiの数が答えとなります。
この配列eをbooleanで取ろうとするとMLEで死んでしまうので、byte配列にしました。

  • ソース
import java.util.Scanner;

//Search of Concatenated Strings
public class AOJ1291 {

	void run(){
		Scanner sc = new Scanner(System.in);
		byte[][] e = new byte[5000][1<<12];
		boolean[][] f = new boolean[5000][12];
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt();
			if((n|m)==0)break;
			String[] s = new String[n];
			for(int i=0;i<n;i++)s[i]=sc.next();
			StringBuilder sb = new StringBuilder();
			while(m--!=0)sb.append(sc.next());
			String t = sb.toString();
			int N = t.length();
			for(int i=0;i<N;i++)for(int j=0;j<1<<n;j++)e[i][j]=0;
			for(int i=1;i<=N;i++){
				String sub = t.substring(0, i);
				for(int j=0;j<n;j++){
					f[i-1][j]=sub.endsWith(s[j]);
					if(f[i-1][j])e[i-1][1<<j]=1;
				}
			}
			int res = 0;
			for(int i=0;i<N;i++)for(int S=0;S<1<<n;S++){
				if(e[i][S]==0)continue;
				if(S==(1<<n)-1)res++;
				for(int j=0;j<n;j++)if(((S>>j)&1)==0){
					if(i+s[j].length()<N&&f[i+s[j].length()][j])e[i+s[j].length()][S|(1<<j)]=1;
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1291().run();
	}
}