1002_trie_failed.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

// dp f[i] = min(f[i - len[k] ])+1 k为1～20
#include <iostream>
#include <string>
using namespace std;

string canReplace[] = {				//数字 -->字母的替换 1 ij	2 abc	3 def 4 gh	5 kl	6 mn 7 prs	8 tuv	9 wxy 0 oqz
							"oqz","ij","abc","def","gh","kl","mn","prs","tuv","wxy"
							};
string numStr;				//数字串
int f[101];					//表示第i-1个字母...的值
int size;
struct node
{
int ptr[26];
bool exist;
} trie[ 5002 ];


void make_trie_tree()
{
	int k, i, j, p, len;
	cin >> k;
	string s;
	memset( trie, 0, sizeof(trie) );
	size=1;
	
	for( i=0; i < k; ++i ) // k is the number of words
	{
	  cin >> s;
	  len = s.length();
	  for( p=1, j=0; j < len ; j++ )
	     {
	     if( trie[p].ptr[ s[j] - 'a' ] == 0 ) trie[p].ptr[ s[j] - 'a' ] = ++size ;
	     p = trie[p].ptr[ s[j] - 'a' ];
	     }
	     trie[p].exist = true ;
	}
}

bool find_trie_len( int start, int len )// start is the beginning of the number array
{
	int i, p;
	
	string s = canReplace[ numStr[start]-'0' ];
//	cout << "numStr[start] : "<<numStr[start] << endl;
	for( p = 1 , i = 0; i < s.length(); i++ )
	{
//		cout << "trie[p].ptr[ s[i] - 'a ] : " << trie[p].ptr[ s[i] - 'a' ] << endl;
		int j = i;
		while( trie[p].ptr[ s[j] - 'a' ] != 0 && len )
		{ 
			cout << "trie[p].ptr[ s[j] - 'a ] : " << trie[p].ptr[ s[j] - 'a' ] << "  len = " <<len <<endl;
			len --;
			p = trie[p].ptr[ s[j] - 'a' ];
			j++;
		}
		if(len == 0 && trie[p].exist == true )
			{cout << true <<endl;return true;}
	}
	return false;
}
int min( int a, int b ){ return a < b ? a : b;} 
void work()
{	
	int i,len;
	f[0] = 0;
	for( i = 1; i <= numStr.length(); i++ )
	{
		int tempf = 0x7f7f7f;
		
		for( len = 1; len <= 20 && i-len >= 0 ; len++ )
			if( find_trie_len(i-len, len) )
				tempf = min(tempf, f[ i - len ] );
		
		if(tempf == 0x7f7f7f)
			f[i] = 0;
		else 
			f[i] = tempf+1;
		cout<< "f[" << i << "]=" << f[i]  << endl;
	}
}

void output()
{
	cout << f[ numStr.length() ] << endl;
}
int main()
{
	while(cin >> numStr,numStr[0]!='-')
	{
		make_trie_tree(); //构造trie字典
		
		//debug
		cout << "trie complete"<<endl;
		cout << numStr << endl;
		for( int i = 1; i <= size ; i++ )
		{	
			cout << "trie[" << i << "] :";
			for( int j = 0 ; j < 26; j++ )
				cout << trie[i].ptr[j] << " ";
			if(trie[i].exist)
				cout << " exist";	
			cout <<endl;
		}
		//end debug 
		
		work();
		output();
	}
	return 0;
}