USACO Training Section 3.1 Contact

英語の原題  
中国語の翻訳
長い01列の中で長さA,Bの間のサブ列の繰り返し回数を探して、順番に最大のN個の繰り返し回数を出力して、しかも相応のサブ列を出力して、同じサブ列が2進数の大きさで並べて出力することを要求します(行ごとに6個).
データ制限:1<=A<=B<=12、1<=N<50、文字列最大長200000
例:
2 4 2
01010010010001000111101100001010011001111000010010011110010000000
出力:
23
00
15
01 10
表示,00が23回で最も多く,次いで01,10が15回ずつ出現した.
明らかにtriesで行うのが最も適切で、長さは最大12で、triesの各ノードは2つのサブノードを含んで、1つの完全な木を構成して、ノード数は2^13-1です.
構想は順調で、書くのも順調ですが、何度も提出して、フォーマットの上でN回の間違いを犯しました.sigh.その後、スレッドのコードを見て、それはtriesで作ったのではなく、ビット操作で、うん、01の特徴を十分に利用して、とても速くて、プログラミングの上でtriesよりも簡単で、特にカウントの時に遍歴する必要はなくて、出力の時ももっと簡単です.確かにtriesを使うより上手です.何が一番適当なのかを改めて示した.教えてもらいました.

/*
ID: blackco3
TASK: contact
LANG: C++
*/
#include <iostream>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define _max_pattern_ 13
#define _max_seq_len_ 200001

char sequence[_max_seq_len_] ;
int seq_size, low, up, n_th ;

struct t_tries {
	int count ;
	t_tries *next[2] ;
} tries_buf[(1<<_max_pattern_)+1] ;
void build_tries( int height ){
	for( int pos=1; pos<(1<<(height+1)); pos++ ){
		tries_buf[pos].count=0;
		if( (pos<<1)>=(1<<(height+1)) )
			tries_buf[pos].next[0] = tries_buf[pos].next[1] = 0 ;
		else 
			tries_buf[pos].next[0] = tries_buf+(pos<<1), tries_buf[pos].next[1] = tries_buf+(pos<<1)+1 ; 
	}
}

struct t_pattern {
	int times, len ;
	char str[_max_pattern_+1];
} patterns[(1<<_max_pattern_)+1], *p_patterns[(1<<_max_pattern_)+1];
typedef t_pattern *tp_pattern ;
int p_pattern_comp( const void * pt1, const void * pt2){
	tp_pattern p1=*(tp_pattern*)pt1, p2=*(tp_pattern*)pt2;
	if( p1->times != p2->times )
		return p1->times - p2->times ;
	if( p1->len != p2->len )
		return p2->len - p1->len ;
	return -strcmp(p1->str, p2->str);
}
int n_pattern=0;
char cur_pattern[_max_pattern_+1];
void get_count( t_tries *pc, int height) {
	if( height>up )
		return ;
	if( height>=low && pc->count ){
		patterns[n_pattern].times = pc->count, patterns[n_pattern].len = height;
		memcpy( patterns[n_pattern].str, cur_pattern, height );
		patterns[n_pattern++].str[height] = '\0' ;
	}
	cur_pattern[height]='0';
	get_count( pc->next[0], height+1 );
	cur_pattern[height]='1';
	get_count( pc->next[1], height+1 );
}

int main() {
	freopen("contact.in", "r", stdin);
	freopen("contact.out", "w", stdout);
	cin >> low >> up >> n_th ;
	char *p_seq=sequence ;
	while (	cin >> p_seq )
		p_seq += strlen( p_seq );
	seq_size = p_seq-sequence ;
	for( p_seq=sequence; *p_seq!='\0'; p_seq++ )
		*p_seq -= '0' ;
	*p_seq = -1 ;
	
	build_tries(up) ;
	char *p_end=p_seq+seq_size-low ;
	for( p_seq=sequence; p_seq<p_end && *p_seq!=-1; p_seq++ ) {
		register t_tries *p_trie=tries_buf+1 ;
		for( register char *pc=p_seq; pc<p_seq+up && *pc!=-1; pc++ )
			p_trie=p_trie->next[*pc], p_trie->count++ ;
	}

	get_count(tries_buf+1,0);
	for( int i=0; i<n_pattern; i++){
		p_patterns[i] = patterns+i ;
	}
	qsort( p_patterns, n_pattern, sizeof(tp_pattern), p_pattern_comp );

	for( int i=n_pattern-1, pre_times=0, pc=0, tc=0; i>=0; i-- ){
		if( pre_times != p_patterns[i]->times ) {
			if( pc && tc ) 
				cout << endl ;
			if( pc==n_th )
				break ;
			cout << p_patterns[i]->times << endl ;
			pre_times=p_patterns[i]->times, pc++, tc=0 ;	
		} 
		if( tc )
			cout << " " ;
		cout << p_patterns[i]->str , tc++;
		if( tc==6 || !i )
			cout << endl , tc=0 ;
	}
	return 0;
}