调试了大半天, 打log打到要吐... 
本以为用trie效率能高一点，没想到还是一样的shi... 2124K	563MS...

哪位大牛帮忙指点指点怎样能优化一下？

#include <iostream>
#include <stack>

using namespace std;

class Trie{
	public:
		bool end;
		Trie *parent;
		Trie *child[26];
		Trie();
		Trie(Trie *p);
		~Trie();
};

Trie::Trie(){
	end = false;
	parent = NULL;
	for(int i = 0; i < 26; ++i){
		if(child[i]){
			child[i] = NULL;
		}
	}
}

Trie::Trie(Trie *p){
	end = false;
	parent = p;
	for(int i = 0; i < 26; ++i){
		if(child[i]){
			child[i] = NULL;
		}
	}
}

Trie::~Trie(){
	for(int i = 0; i < 26; ++i){
		if(child[i]){
			delete child[i];
			child[i] = NULL;
		}
	}
}

void AddWord(string s, Trie &t){
	int len = s.size();
	Trie *p = &t;
	for(int i = 0; i < len; ++i){
		int index = s[i] - 97;
		if(p->child[index] == NULL){
			p->child[index] = new Trie(p);
		}
		p = p->child[index];
	}
	p->end = true;
}

//找当前节点的下一个兄弟节点
int NextChild(Trie *prev, Trie **Child){
	int pos = -1;
	if(prev!=NULL){
		for(int i = 0; i < 26; ++i){
			if(Child[i] == prev) pos = i;
		}
	}
	for(int i = pos + 1; i < 26; ++i){
		if(Child[i] != NULL) return i;
	}
	return -1;
}

int main(){
	int w_count, msg_len; cin>>w_count>>msg_len;
	string s[600];
	string msg;
	cin>>msg;
	for(int i = 0; i < w_count; ++i){
		cin>>s[i]; 
	}
	Trie t;
	for(int i = 0; i < w_count; ++i){
		AddWord(s[i], t);
	}
	int len = msg.size();
	//Begin match
	stack<short> pos_st; //记录匹配的字符对应msg中的位置，以便将来回溯用
	short d[300]; 
	d[len] = 0;
	int index = msg[len-1] - 97;
	if(t.child[index] && t.child[index]->end){
		d[len-1] = 0;
	}else{
		d[len-1] = 1;
	}
	for(int k = len - 2; k >= 0; --k){
		index = msg[k] - 97;
		if(t.child[index] == NULL){
			d[k] = d[k+1] +1; continue;
		}else{
			if(t.child[index]->end){
				d[k] = d[k+1];
			}else{
				d[k] = d[k+1] +1;
			}
		}
		Trie *cur; Trie *first;
		first = cur = t.child[index];
		Trie *prev = &t;
		int i;
		pos_st.push(k);
		int removed = 0;
		while(true){
			int i = pos_st.top() + 1;
			int next;
			if(prev == cur->parent){ 
				next= NextChild(NULL, cur->child);
			}else{
				next = NextChild(prev, cur->child);
			}
			if(next < 0){
				if(cur == first){
					break;
				}else{ 
					i = pos_st.top(); pos_st.pop();
					int recent_rmv = i - pos_st.top() -1; // 如果当前字符没有需要匹配的儿子，回退到上一字符。removed 也相应减去两个字符之间的字符。
					removed -= recent_rmv;
					i = pos_st.top(); 
					prev = cur; cur = cur->parent;
					continue;
				}
			}
			while(true){
				if(msg[i]-97 == next){
					if(cur->child[next]->end){ // 如果成功匹配了一个单词，则看remove +d[i+1]是否构成d[k]的最优解
						if(removed + d[i+1] < d[k])
							d[k] = removed + d[i+1];
					}
					if(i < len -1){
						prev = cur; cur = cur->child[next]; //继续匹配单词的下一个字符
						pos_st.push(i++); break;						
					}else{
						int recent_rmv = i - pos_st.top() -1; //如果匹配到字串最后一个字符，则回退考察当前节点的兄弟节点
						removed -= recent_rmv; 
						prev = cur->child[next]; break;
					}
				}else{
					removed++; 
					if(removed >= d[k] | i == len -1){ //如果removed字符超过d[k]，或者已经越过字串最后一个字符，则放弃匹配单词的当前字符
						int recent_rmv = i - pos_st.top(); 
						removed -= recent_rmv; 	
						prev = cur->child[next]; break;
					}
					i++;
				}
			}
		}
	}
	cout<<d[0]<<'\n';
}

• Re:DP + Trie, 做了两天... 上shi一样的代码... (9) 150137 2016-08-17 15:01:18