AOJ-1170: Old Memories (古い記憶)

keyword

ハッシュ　定数倍最適化　C++

問題概要

長さM(<40)以下の文字列が与えられる。また、長さL(13<=L<=20)の文字列がN(<30)個あたえられる。もとの文字列からの編集距離が2以下のもので、N個の文字列にすべて被覆されるようなものが何種類あるか求める問題。テストケース100個位。

解法

ICPC的には、編集距離2以下の文字列を全部作って、カバーされるかどうか確かめればよい。カバーされるかどうか確かめる部分は、Lが一定なことを利用してRabin-Karpっぽくローリングハッシュでハッシュ値が一致するか見ればよい(もちろん衝突の可能性があるが、値の範囲を大きくすればその確率は下げられる)。これで一応5分くらいまてば正解はでる。ただし自分の環境だとJavaではフリーズした。new String()を何度も呼んでGCが大忙しで…とかなったせいだと思う。この辺の処理の上手いやり方はよく分からない。
で、AOJ的には8秒で答えを返すように高速化しなければならない。重いテストケースは元の文字列が全部同じやつなのでそれに絞って対策した(これに気づいたのは公開されてる入力データを呼んだからなのでインチキしている)。最後のあと1秒の高速化が大変だったけど、最後はvectorのリザーブとset->ハッシュテーブルへの置き換えが決め手だった。ソースコードの汚さがまた過去最低を更新した気がする。実装時間はいっぱい。
もう少し真面目に枝刈りする方法を考えると、入れ替えたときに入力が変化しないような2文字間に同値関係を入れて最後に適当に掛け算するとかがまともな方法な気がする。たぶん気がするだけだと思う。

感想

探索の枝刈りってセンスを問われているような気がして、この問題であまり枝を刈れなかったことに少し凹んでいる。それにしてもコード汚すぎ and 実装に時間かけすぎで、これ全然練習になってないよね、と自覚しながらも意地になって時間をかけた。こんな風にダラダラとやってしまうのは自分がオンラインジャッジの問題を解く上での悪癖だと思う。

#include <cstdio>
#include <vector>
#include <set>
#include <string>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string.h>
using namespace std;

typedef unsigned long long ul;

const ul base = 1000000007;
vector<ul> bs;
set<string> ans;
set<ul> ans2;
string line;
vector<ul> hs;
vector<string> piece;
set<string> d1, d2;
string plane;
bool precheck[0x100][0x100][0x100];
int N, d, L;
bool cut;
bool preok[50], postok[50];
bool preok2[50][0x100], postok2[50][0x100];
int prewidth[0x100], postwidth[0x100];
int precut, postcut, width;
bool oks[50], covered[50];

inline ul hash_func(string& str){
	ul ret = 0;
	for(int i=0; i<L; i++){
		ret += str[i] * bs[L-1-i];
	}
	return ret;
}

inline ul hash_func2(string& str){
	ul ret = 0;
	for(int i=0; i<str.length(); i++){
		ret += bs[i] * str[i];
	}
	return ret;
}

inline void add_ans(string& str){
	ans2.insert(hash_func2(str));
	if(ans.size()<=4){
		ans.insert(str);
	}
}

inline bool check(string& str){
	int n = str.length();
	if(n < L){
		return false;
	}
	ul h = hash_func(str);
	memset(oks,0,sizeof(oks));
	memset(covered,0,sizeof(covered));
	if(binary_search(hs.begin(), hs.end(), h)){
		oks[0] = true;
	}
	for(int i=0; i<n-L; i++){
		h = h*base - bs[L]*str[i] + str[i+L];
		if(binary_search(hs.begin(), hs.end(), h)){
			oks[i+1] = true;
		}
	}
	for(int i=0; i<n; i++)if(oks[i]){
		for(int j=0; j<L; j++){
			covered[i+j] = true;
		}
		if(!covered[i]){
			//if((rand()&0xfff)<10) cout << str << endl;
			return false;
		}
	}
	for(int i=0; i<n; i++)if(!covered[i]){
		//if((rand()&0xfff)<10) cout << str << endl;
		return false;
	}
	return true;
}

void generate(string& str, set<string>& dd){
	int difpos;
	bool phase2 = (&dd == &d2);
	if(cut){
		if(!phase2){
			dd.insert(str + string(1,line[0]));
			dd.insert(string(1,line[0]) + str);
		}
		else {
			string t = str + string(1,line[0]);
			if(check(t)) add_ans(t);
			t = string(1,line[0]) + str;
			if(check(t)) add_ans(t);
		}
		difpos = str.find_first_not_of(line[0]);
	}
	int n = str.length();
	//insert
	for(int i=0; i<n+1; i++){
		if(cut && difpos != string::npos){
				if(difpos<L-1 && !preok2[difpos][str[difpos]]){
					if(!(preok2[difpos+1][str[difpos]] && i<difpos)) continue;
				}
				if(n-1-difpos<L-1 && !postok2[n-1-difpos][str[difpos]]){
					if(!(postok2[n-difpos][str[difpos]] && i>=difpos)) continue;
				}
		}
		if(cut && (i<=precut-1 || n-i-1<=postcut-2)) continue;
		if(cut && difpos != string::npos && abs(difpos - i) <= width) continue;
		if(cut && difpos != string::npos && prewidth[str[difpos]] && difpos - i <= prewidth[str[difpos]] - 1 && i <= difpos) continue;
		if(cut && phase2 && i<L && !preok[i]) continue;
		if(cut && phase2 && n-i-1<L && !postok[n-i]) continue;
		if(cut && i < L && i>0 && !(preok[i-1] || preok[i])) continue;
		if(cut && n-1-i < L && i<n-1 && !(postok[n-i] || postok[n-i+1])) continue;
		string t;t.reserve(n+1);
		for(int j=0; j<n; j++){
			if(j==i) t.push_back('.');
			t.push_back(str[j]);
		}
		if(i==n) t.push_back('.');
		for(char c='.';c<='.';c++){
			if(cut && phase2 && i<L && !preok2[i][c]) continue;
			if(cut && phase2 && n-i-1<L && !postok2[n-i][c]) continue;
			if(cut && i<L-1 && i>0 && !(preok2[i-1][c] || preok2[i][c] || preok2[i+1][c])) continue;
			if(cut && n-i-1<L-1 && n-i>0 && !(postok2[n-i-1][c] || postok2[n-i][c] || postok2[n-i+1][c])) continue;
			if(i==0 || i==n || (precheck[t[i-1]][t[i]][t[i+1]])){
				if(phase2){
					if(check(t)) add_ans(t);
				}
				else{
					dd.insert(t);
				}
			}
		}
		for(char c='A'; c<='Z'; c++){
			t[i] = c;
			if(cut && phase2 && i<L && !preok2[i][c]) continue;
			if(cut && phase2 && n-i-1<L && !postok2[n-i][c]) continue;
			if(cut && i<L-1 && i>0 && !(preok2[i-1][c] || preok2[i][c] || preok2[i+1][c])) continue;
			if(cut && n-i-1<L-1 && n-i>0 && !(postok2[n-i-1][c] || postok2[n-i][c] || postok2[n-i+1][c])) continue;
			if(i==0 || i==n || (precheck[t[i-1]][t[i]][t[i+1]])){
				if(phase2){
					if(check(t)) add_ans(t);
				}
				else{
					dd.insert(t);
				}
			}
		}
	}

	//replace
	if(!(cut && difpos != string::npos &&
			((difpos<L && !preok2[difpos][str[difpos]]) || (n-1-difpos<L && !postok2[n-1-difpos][str[difpos]]))))
	for(int i=0; i<n; i++){
		if(cut && (i<=precut-1 || n-i-1<=postcut-1)) continue;
		if(cut && difpos != string::npos && abs(difpos - i) <= width) continue;
		if(cut && difpos != string::npos && prewidth[str[difpos]] && difpos - i <= prewidth[str[difpos]] - 1 && i <= difpos) continue;
		if(cut && phase2 && i<L && !preok[i]) continue;
		if(cut && phase2 && n-1-i<L && !postok[n-i-1]) continue;
		if(cut && i < L && i>0 && !(preok[i-1] || preok[i])) continue;
		if(cut && n-1-i < L && i<n-1 && !(postok[n-i-2] || postok[n-i-1] )) continue;
		string t = str;
		for(char c='.';c<='.';c++){
			t[i] = c;
			if(cut && phase2 && i<L && !preok2[i][c]) continue;
			if(cut && phase2 && n-i-1<L && !postok2[n-i-1][c]) continue;
			if(cut && i<L-1 && i>0 && !(preok2[i-1][c] || preok2[i][c] || preok2[i+1][c])) continue;
			if(cut && n-i-1<L-1 && n-i-1>0 && !(postok2[n-i-2][c] || postok2[n-i-1][c] || postok2[n-i][c])) continue;
			if(i==0 || i==n-1 || (precheck[t[i-1]][t[i]][t[i+1]])){
				if(phase2){
					if(check(t)) add_ans(t);
				}
				else{
					dd.insert(t);
				}
			}
		}
		for(char c='A'; c<='Z'; c++){
			t[i] = c;
			if(cut && phase2 && i<L && !preok2[i][c]) continue;
			if(cut && phase2 && n-i-1<L && !postok2[n-i-1][c]) continue;
			if(cut && i<L-1 && i>0 && !(preok2[i-1][c] || preok2[i][c] || preok2[i+1][c])) continue;
			if(cut && n-i-1<L-1 && n-i-1>0 && !(postok2[n-i-2][c] || postok2[n-i-1][c] || postok2[n-i][c])) continue;
			if(i==0 || i==n-1 || (precheck[t[i-1]][t[i]][t[i+1]])){
				if(phase2){
					if(check(t)) add_ans(t);
				}
				else{
					dd.insert(t);
				}
			}
		}
	}

	//delete
	for(int i=0; i<n; i++){
		string t;t.reserve(n);
		for(int j=0; j<n; j++){
			if(i!=j) t.push_back(str[j]);
		}
		if(phase2){
			if(check(t)) add_ans(t);
		}
		else{
			dd.insert(t);
		}
	}
}

inline void add(string& t, int ind){
	if(check(t)) add_ans(t);
	for(char c='A';c<='Z';c++){
		t[ind] = c;
		if(check(t)) add_ans(t);
	}
	t[ind] = '.';
	for(char c='A';c<='Z';c++){
		t[ind+1] = c;
		if(check(t)) add_ans(t);
	}
	for(char c='A';c<='Z';c++){
		for(char cc='A';cc<='Z';cc++){
			t[ind] = c;
			t[ind+1] = cc;
			if(check(t)) add_ans(t);
		}
	}
}

void subsolve(){
	//insert-insert
	int n = line.length();
	for(int i=0; i<n+1; i++){
		string t;
		for(int j=0; j<n; j++){
			if(i==j) t += "..";
			t.push_back(line[j]);
		}
		if(i==n) t += "..";
		add(t,i);
	}
	//insert-replace
	for(int i=0; i<n; i++){
		string t;
		for(int j=0; j<n; j++){
			if(i==j) t.push_back('.');
			t.push_back(line[j]);
		}
		t[i+1] = '.';
		add(t,i);
	}
	//replace-insert
	for(int i=0; i<n; i++){
		string t;
		for(int j=0; j<n; j++){
			if(i+1==j) t.push_back('.');
			t.push_back(line[j]);
		}
		if(i==n-1) t.push_back('.');
		t[i] = '.';
		add(t,i);
	}
	//replace-replace
	for(int i=0; i<n-1; i++){
		string t = line;
		t[i] = t[i+1] = '.';
		add(t,i);
	}
}

void solve(){
	cut = true;
	for(int i=0; i<line.length()-1; i++){
		if(line[i] != line[i+1]) cut = false;
	}
	if(cut){
		vector<string> cats;
		cats.reserve(30*30*20*20);
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				cats.push_back(piece[i] + piece[j]);
				for(int k=0; k<L; k++){
					string pre = piece[i].substr(k);
					for(int l=0; l<L; l++){
						string post = piece[j].substr(0,pre.length());
						if(pre == post){
							cats.push_back(piece[i] + piece[j].substr(pre.length()));
						}
					}
				}
			}
		}
		sort(cats.begin(), cats.end());
		cats.erase(unique(cats.begin(), cats.end()), cats.end());
		width = 1<<10;
		for(typeof(cats.begin()) itr = cats.begin(); itr != cats.end(); itr++){
			string t = *itr;
			for(int i=0; i<t.length(); i++)if(t[i] != line[0]){
				preok[i] = true;
				preok2[i][t[i]] = true;
			}
			for(int i=0; i<t.length(); i++)if(t[t.length()-1-i] != line[0]){
				postok[i] = true;
				postok2[i][t[t.length()-1-i]] = true;
			}
			int pre = t.find_first_not_of(line[0]), post = t.find_last_not_of(line[0]);
			if(pre != post){
				width = min(width, post - pre - 1);
				prewidth[t[post]] = max(prewidth[t[post]], post - pre - 1);
				postwidth[t[pre]] = max(postwidth[t[pre]], post - pre - 1);
			}
		}
		if(width == 1<<10) width = 0;
		precut = L;
		for(int i=0; i<N; i++){
			for(int j=0; j<L; j++)if(piece[i][j] != line[0]){
				precut = min(precut, j);
				break;
			}
		}
		postcut = L;
		for(int i=0; i<N; i++){
			for(int j=0; j<L; j++)if(piece[i][L-1-j] != line[0]){
				postcut = min(postcut, j);
				break;
			}
		}
		if(0){
			cout << width << endl;
			cout << precut << endl;
			cout << postcut << endl;
		}
	}
	for(int i=0; i<N; i++){
		for(int j=1; j<L-1; j++){
			precheck[piece[i][j-1]][piece[i][j]][piece[i][j+1]] = true;
		}
	}
	for(int i=0; i<N; i++){
		for(int k=0; k<N; k++){
			precheck[piece[i][L-2]][piece[i][L-1]][piece[k][0]] = true;
			precheck[piece[k][L-1]][piece[i][0]][piece[i][1]] = true;
		}
	}
	for(int i=0; i<N; i++){
		hs.push_back(hash_func(piece[i]));
	}
	sort(hs.begin(), hs.end());
	if(check(line)){
		add_ans(line);
	}
	if(d<1) return ;
	generate(line, d1);
	for(typeof(d1.begin()) itr = d1.begin(); itr != d1.end(); itr++){
		string tmp = *itr;
		if(check(tmp)) add_ans(tmp);
	}
	if(d<2) return ;
	for(typeof(d1.begin()) itr = d1.begin(); itr != d1.end(); itr++){
		string tmp = *itr;
		generate(tmp, d2);
	}
	if(!cut || width==0)subsolve();
}

void print(){
	printf("%d\n", (int)ans2.size());
	if(ans2.size() <= 5){
		for(typeof(ans.begin()) itr = ans.begin(); itr != ans.end(); itr++){
			puts(itr->c_str());
			//cout << *itr << endl;
		}
	}
}

void init(){
	cut = false;
	plane = "";
	d1.clear();
	d2.clear();
	ans.clear();
	ans2.clear();
	hs.clear();
	piece.clear();
	for(int i=0; i<50; i++) preok[i] = postok[i] = false;
	for(int i=0; i<0x100; i++) prewidth[i] = postwidth[i] = 0;
	for(int i=0; i<50; i++)for(int j=0; j<0x100; j++) preok2[i][j] = postok2[i][j] = false;
	for(int i=0; i<0x100; i++){
		for(int j=0; j<0x100; j++){
			for(int k=0; k<0x100; k++){
				precheck[i][j][k] = false;
			}
		}
	}
}


int main(){
	bs.push_back(1);
	for(int i=0; i<60; i++){
		bs.push_back(bs.back()*base);
	}
	while(scanf("%d%d ",&d,&N)){
		if(d==0 && N==0) break;
		init();
		getline(cin,line);
		piece.clear();
		for(int i=0; i<N; i++){
			string t;
			getline(cin,t);
			piece.push_back(t);
		}
		L = piece[0].size();
		solve();
		print();
	}
	fflush(stdout);
	return 0;
}