AOJ-1227, POJ-1409: 77377

keyword

動的計画法　経路復元　C++

問題概要

よくある携帯電話の入力方式の問題。打ち込んだ数字列と辞書が与えられるのでマッチングする文章を全て出力する問題。

解法

前からDPしていく。経路復元は定石どおりDPテーブルにどこから来たのか情報を付記しておけばよい（というか、今回はその情報さえあればよい）。気分としてはTCO2011 Qual1-A 500pt: FoxListeningToMusicに近い気がする。ハッシュ値使ったり前処理を工夫したら計算量落とせそう。
AOJとPOJで出力の制限が微妙に異なるので注意。以下はAOJで通ったコード。

#include <cstdio>
#include <string>
#include <vector>
using namespace std;

int N;
char table[0x100];
string ws[109];
string encoded[109];
int ls[109];
string input;

vector<int> prev[309];
int ans[309];
int p;

void solve(){
	int len = input.length();
	for(int i=0; i<len; i++){
		for(int j=0; j<N; j++){
			if(i + ls[j] <= len && input.substr(i,ls[j]) == encoded[j]){
				prev[i+ls[j]].push_back(j);
			}
		}
	}
}

void dfs(int pos){
	if(pos<=0){
		for(int i=p-1; i>=0; i--){
			printf("%s%s",ws[ans[i]].c_str(),i?" ":".\n");
		}
		return ;
	}
	if(prev[pos].empty()){
		return ;
	}

	for(int i=0; i<(int)prev[pos].size(); i++){
		ans[p++] = prev[pos][i];
		dfs(pos - ls[prev[pos][i]]);
		p--;
	}
	return ;
}

string translate(string str){
	for(int i=0, len=str.length(); i<len; i++){
		str[i] = table[str[i]];
	}
	return str;
}

void init(){
	for(int i=0; i<309; i++) prev[i].clear();
	p = 0;
	for(int i=0; i<N; i++){
		ls[i] = ws[i].length();
		encoded[i] = translate(ws[i]);
	}
}

int main(){
	table['a'] = table['b'] = table['c'] = '2';
	table['d'] = table['e'] = table['f'] = '3';
	table['h'] = table['i'] = table['g'] = '4';
	table['j'] = table['k'] = table['l'] = '5';
	table['m'] = table['n'] = table['o'] = '6';
	table['p'] = table['q'] = table['r'] = table['s'] = '7';
	table['t'] = table['u'] = table['v'] = '8';
	table['w'] = table['x'] = table['y'] = table['z'] = '9';

	while(scanf("%d ",&N),N){
		char buf[1025];
		for(int i=0; i<N; i++){
			scanf("%s ",buf);
			ws[i] = string(buf);
		}
		scanf("%s ",buf);
		input = string(buf);
		init();
		solve();
		dfs((int)input.length());
		puts("--");
	}
	return 0;
}