잠이 안와서 문제 기억나는대로 기초코딩 해봤다.
뭐 답은 금세 나오는데?
#include <iostream>
#include <vector>
using namespace std;
const char value_to_symbol[] =
"0123456789"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
const char symbol_to_value[] =
{
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
0x08, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10,
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x20,
0x21, 0x22, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A,
0x2B, 0x2C, 0x2D, 0x2E, 0x2F, 0x30, 0x31, 0x32,
0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A,
0x3B, 0x3C, 0x3D, 0x00, 0x00, 0x00, 0x00, 0x00,
};
char input_string[1024 * 1024 + 1];
#define SYMBOL_COUNT ( sizeof value_to_symbol - 1 )
size_t input_length = 0;
size_t hi_score = 0;
size_t hi_score_length = 0;
size_t hi_score_count = 0;
void check_next( vector< size_t >& location_list, size_t offset )
{
int list_count = location_list.size();
vector< size_t >* location_lists = new vector< size_t >[SYMBOL_COUNT];
for( int i = 0; i < list_count; ++i )
{
size_t location = location_list[i] + offset;
if( location >= input_length ) break;
size_t symbol = symbol_to_value[ input_string[location] ];
location_lists[symbol].push_back( location_list[i] );
}
for( int i = 0; i < SYMBOL_COUNT; ++i )
{
int cnt = location_lists[i].size();
int len = offset + 1;
size_t score = cnt * len;
if( hi_score < score )
{
hi_score_length = len;
hi_score_count = cnt;
hi_score = score;
}
if( cnt > 1 && cnt * input_length > hi_score )
{
check_next( location_lists[i], offset + 1 );
}
location_lists[i].clear();
}
delete[] location_lists;
}
void parse_string( char* s, size_t length )
{
input_length = length;
vector< size_t >* location_lists = new vector< size_t >[SYMBOL_COUNT];
hi_score = 0;
for( int i = 0; i < length; ++i )
{
size_t value = symbol_to_value[ s[i] ];
location_lists[ value ].push_back( i );
}
for( int i = 0; i < SYMBOL_COUNT; ++i )
{
if( location_lists[i].size() > 1 )
check_next( location_lists[i], 1 );
}
delete[] location_lists;
}
void build_string( char* s, size_t length )
{
for( int i = 0; i < length; ++i )
s[i] = value_to_symbol[rand() % SYMBOL_COUNT];
input_string[length] = 0;
}
int main()
{
build_string(input_string, 1024 * 1024);
parse_string(input_string, 1024 * 1024);
cout << "hi_score = " << hi_score << endl;
cout << "length = " << hi_score_length << endl;
cout << "count = " << hi_score_count << endl;
getchar();
return 0;
}
댓글 0