2934.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2934  User Id:fzk 
Memory:20672K  Time:968MS
Language:G++  Result:Accepted

Source 

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
#include <hash_map.h>
using namespace std;

struct str_hash{
        size_t operator()(const string& str) const
        {
                unsigned long __h = 0;
                for (size_t i = 1 ; i < str.size() ; i ++)
                if( i != str[0]-'0' )
                	__h = 27*__h + str[i];
                return size_t(__h);
        }
};

struct eq {
	bool operator()( const string &a, const string &b ) const {
		for( unsigned int i=1, j=1;; i++, j++ ) {
			if( i==unsigned(a[0]-'0') ) i++;
			if( j==unsigned(b[0]-'0') ) j++;
			if( i>=a.length() && j>=b.length() )
		 		return true;
		 	if( i>=a.length() || j>=b.length() || a[i] != b[j] )
		 		return false;
		}
	}
};

char w[10100][30];
int n;

hash_map<string, int, str_hash, eq> s;

void fill( string str, int index ) {
	int n = str.length(), i;
	char c;
	
	s[str] = -index-1;
		
	for( i=1; i<n; i++ ) {
		str[0] = '0'+i;
		if( s.find( str ) == s.end() )
			s[str] = index;
	}
	
	str[0] = '0';
	for( i=1; i<n; i++ ) {
		c = str[i];
		str[i] = '_';
		if( s.find( str ) == s.end() )
			s[str] = index;
		str[i] = c;
	}
}

int main( ){
	int n, i, j, m, ans, l;
	char word[100], c;
	string str;
	hash_map<string, int, str_hash, eq>::iterator it;

	scanf( "%d", &n );
	s.resize( n*60 );

	for( i=0; i<n; i++ ) {
		scanf( "%s", w[i]+1 );
		w[i][0] = '0';
		fill( w[i], i );
	}
	//printf( "%d\n", s.find( "0dictonary" ) == s.end() );
	
	scanf( "%d", &m );
	for( i=0; i<m; i++ ) {
		scanf( "%s", word+1 );
		word[0] = '0';
		str = word;
		l = str.length();
		ans = -1;
		
		if( (it = s.find( str )) != s.end() ) {
			if( it->second < 0 ) {
				printf( "%s is correct\n", word+1 );
				continue;
			}
			ans = it->second;
		}
		
		for( j=1; j<l; j++ ) {
			str[0] = '0';
			c = str[j];
			str[j] = '_';
			if( (it = s.find( str )) != s.end() ) {
				if( ans < 0 || it->second < ans )
					ans = it->second;
			}
			str[j] = c;
			
			str[0] = '0'+j;
			if( (it = s.find( str )) != s.end() && it->second < 0 )
				if( ans < 0 || -it->second-1 < ans )
					ans = -it->second - 1;
		}
		
		str[0] = '0';
		for( j=1; j<l-1; j++ ) {
			swap( str[j], str[j+1] );
			if( (it = s.find( str )) != s.end() && it->second < 0 )
				if( ans < 0 || -it->second-1 < ans )
					ans = -it->second - 1;
			swap( str[j], str[j+1] );
		}
		
		if( ans < 0 )
			printf( "%s is unknown\n", word+1 );
		else
			printf( "%s is a misspelling of %s\n", word+1, w[ans]+1 );
	}
	return 0;