AOJ 1170 Time Limit Excceed

AOJ1170.cpp

#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <tr1/unordered_set>
#include <map>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

typedef unsigned long long lli;
int dp_edit[52][52];

set<lli> visited[44];

int edit_distance(const string &a, const string &b, int insert_cost = 1,
		int replace_cost = 1, int remove_cost = 1) {
	memset(dp_edit,0,sizeof(dp_edit));
	REP(i,a.size()+1){
		dp_edit[i][0]=insert_cost*i;
	}
	REP(j,b.size()+1){
		dp_edit[0][j]=remove_cost*j;
	}
	for(int i=1;i<=(int)a.size();i++){
		for(int j=1;j<=(int)b.size();j++){
			int rcost=replace_cost;
			if(a[i-1]==b[j-1])rcost=0;
			dp_edit[i][j]=min(dp_edit[i-1][j]+insert_cost,
					min(dp_edit[i][j-1]+remove_cost,
							dp_edit[i-1][j-1]+rcost));
		}
	}
	return dp_edit[a.size()][b.size()];
}
int d,n,m;
string input;
string piece[30];
vector<int> connect[50][50];
set<string> memo[44][44];

struct State{
	int length;
	lli hash;
	vector<int> edist;
	int last;
	State add_char(char s){ // 一文字追加する。
		int nlen = this->length + 1;
		lli nhash = this->hash * 39 + s - 64;
		vector<int> nedit(input.size()+1);
		nedit[0] = nlen;
		for(int j = 1; j <= (int)input.size(); j++){
			int c = 1;
			if(s == input[ j - 1]) c = 0;
			nedit[j] = min(edist[j] + 1, min(nedit[j-1] + 1,edist[j - 1] + c));
		}
		return (State){nlen,nhash,nedit};
	}
	const int min_dist() const{
		int ret=9999;
		for(int i=max(length - d, 0); i <= min(length + d, (int)input.size()) ;i++){
			ret=min(ret,edist[i]);
		}
		return ret;
	}
	const bool is_valid() const{
		if(length > input.size() + 2)return false;
		if(visited[length].find(hash) != visited[length].end()) return false;
		if(min_dist() <= d)return true;
		return false;
	}
};
bool operator<(const State &a,const State &b){
	return a.length < b.length;
}

bool operator>(const State &b,const State &a){
	return a < b;
}
void solve(){
	REP(i, 44)visited[i].clear();
	REP(i,n){
		REP(j,n){
			connect[i][j].clear();
			assert(piece[0].size() == piece[i].size());
			REP(k,piece[0].size()){
				string back=piece[j].substr(0,k);
				string first=piece[i].substr(piece[i].size()-k);
				if(back==first){
					connect[i][j].push_back(k);
				}
			}
		}
	}

	priority_queue<State, vector<State>, greater<State> > que;
	State first={0, 0, vector<int>(input.size() + 1,0)};
	REP(i, input.size() + 1){
		first.edist[i] = i;
	}
	REP(i, n){
		State tmp = first;
		REP(j, piece[i].size()){
			tmp = tmp.add_char(piece[i][j]);
		}
		tmp.last = i;
		if(tmp.is_valid())
			que.push(tmp);
		//REP(j, tmp.edist.size()){
		//	cout << tmp.edist[j] << " ";
		//}
		//cout << endl;
		que.push(tmp);
		visited[tmp.length].insert(tmp.hash);
	}
	int ans=0;
	vector<lli> tmps;
	while(!que.empty()){
		State now = que.top(); que.pop();
		tmps.push_back(now.hash);
//		cout << now.min_dist() << endl;
//		cout << que.size() << endl;
		if(now.edist[input.size()] <= d) ans++;
//		cout << now.length << endl;
		REP(next, n){
			REP(k, connect[now.last][next].size()){
				int dst = connect[now.last][next][k];
				State nex = now;
				for(int i = dst; i < (int)piece[next].size();i++){
					nex = nex.add_char(piece[next][i]);
				}
				nex.last = next;
				if(nex.is_valid()){
					que.push(nex);
					visited[nex.length].insert(nex.hash);
				}
			}
		}
	}
	cout <<ans << endl;
}
int main() {
	while(cin>>d>>n){
		if(d==0&&n==0)break;
		assert(1<=d&&d<=2);
		assert(1<=n&&n<=30);
		cin>>input;
		//cout<<input<<endl;
		m=input.size();
		REP(i,n){
			cin>>piece[i];
		}
		// 重複消去
		REP(i,n){
			int found=false;
			REP(j,i){
				if(piece[i]==piece[j]){
					found=true;
				}
			}
			if(found){
				for(int j=i;j<n-1;j++){
					piece[j]=piece[j+1];
				}
				n--;i--;
			}
		}
		solve();
	}

	return 0;
}