Google Code Jam 2013 Round 1B : C. Garbled Email

さてC。いつもと違い大容量データが与えられる。
https://code.google.com/codejam/contest/2434486/dashboard#s=p2

問題

まず、全問共通で用いる辞書データDが与えられる。これらは52万語・5MBとかなり多い。
ここで、最大4000文字の文字列Sが与えられる。この文字列は辞書にある単語を連結して作られているが、途中いくつか誤字がある。
ただし誤字同士は最小でも5文字(=M)空いている。

このとき、文字列を辞書中の単語の連結で表現するときに修正が必要な最少の誤字数を求める。

解法

直前の文字修正位置を用いたDPを行えばよい。
直前の文字修正位置から5文字以上離れた場所を修正することで、辞書中の単語とマッチするかどうかを調べていく。
単語は5文字以上のものもあるため、１語で複数誤字がある場合もあることに注意。
(smallはこの条件が無くても通ってしまい、Largeで通らず苦戦した)

単語とSのマッチ処理は特に高速化は行わず、52万語の単語に対し1文字ずつ比較を行った。
この場合平均単語長をLとすると、この処理はO(SLM)程度かかる。

この場合Largeでは1caseで18秒もかかったが、幸いテストケースが4つしかないので問題ない。
ただ、C系じゃないスクリプト言語では何かしらの高速化が必要そうだ。

vector<string> SL;
const char* hoge[] = {
"a",
"aa",
"aaaamau",
(略・辞書データ)
"zymuyi",
"zymuznh",
"" };

void solve(int _loop) {
	int i,j,x,y,ne=0;
	int NP,TP,PP;
	char str[5000];
	int DP[5000][6];
	int L;
	
	GETs(str);
	L=strlen(str);
	FOR(x,5000) FOR(y,6) DP[x][y]=99999;
	DP[0][0]=0;
	
	FOR(i,L) {
		int ok=0;
		FOR(x,SL.size()) {
			int ss = SL[x].size();
			if(i+ss>L) continue;
			
			int st=-1,ed=-1,num=0;
			FOR(y,ss) {
				if(str[i+y]!=SL[x][y]) {
					if(num && y-ed<4) {
						num=-1;
						break;
					}
					if(st==-1) st=y+1;
					ed=y+1;
					num++;
				}
			}
			
			if(num==-1) continue;
			if(num==0) {
				FOR(y,6) DP[i+ss][max(0,y-ss)] = min(DP[i+ss][max(0,y-ss)], DP[i][y]);
			}
			else {
				FOR(y,6) if(st>=y) DP[i+ss][max(0,5+ed-ss)] = min(DP[i+ss][max(0,5+ed-ss)], num+DP[i][y]);
			}
		}
	}
	
	int mi=99999;
	FOR(y,6) mi=min(mi,DP[L][y]);
	_PE("Case #%d: %d\n",_loop,mi);
	
}

まとめ

大容量の単語データをDLさせるのは珍しいけど、あとは単なるDPだな…。
C++だと文字列一致は愚直にやっても間に合ったけど、本当は文字列検索でもっと高速化することを想定してたのかな？