2408.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2408 on 2006-10-25 at 20:04:12 */
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

const int L = 1 << 20;

char word[L];
int next[L];

void radix(int*, char*, int);

int main()
{
	int T;
	
	scanf("%d\n", &T);
	for(int t = 0; t < T; t++) {
		int len = 0;
		while(true) {
			char c = getchar(), d;
			if(c == '\n') break;
			word[len++] = c;
			d = getchar();
			if(d == '\n') break;
			else {
				ungetc(d, stdin);
				if(!isdigit(d)) continue;
				int k; scanf("%d", &k);
				for(int i = 1; i < k; i++) word[len++] = c;
			}
		}
		radix(next, word, len);
		int id = 0;
		for(int i = 0; i < len; i++)
			if(word[i] == '.') { id = i; break; }
		id = next[id];
		for(int i = 0; i < len; i++, id = next[id])
			putchar(word[id]);
		putchar('\n');
	}
	
	return 0;
}

void radix(int* nxt, char* w, int l)
{
	int c[32] = { 0 };
	for(int i = 0; i < l; i++) {
		int cx = (word[i] == '.' ? 0 : word[i]-'A'+1);
		c[cx]++;
	}
	for(int i = 0, sum = 0; i < 32; i++) 
		{ int t = c[i]; c[i] = sum; sum += t; }
	for(int i = 0; i < l; i++) {
		int cx = (word[i] == '.' ? 0 : word[i]-'A'+1);
		nxt[c[cx]++] = i;
	}
}