2114.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2114 on 2005-12-18 at 12:52:57 */ 
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX = 128;

bool isNecklace(const string&);
bool merge(vector<string>&);

int main()
{
	vector<string> neck;
	char line[MAX];
	int t, T, i;
	
	scanf("%d\n", &T);
	for(t = 0; t < T; t++) {
		neck.clear();
		gets(line);
		for(i = 0; line[i] != 0; i++) {
			neck.push_back(string(line+i, line+i+1));
		}
		while(merge(neck)) ;
		vector<string>::iterator it;
		for(it = neck.begin(); it != neck.end(); it++) {
			cout << "(" << *it << ")";
		}
		putchar('\n');
	}
	
	return 0;
}

bool isNecklace(const string& s)
{
	int i, j, n = s.size();
	for(i = 1; i < n; i++) {
		for(j = 0; j < n; j++) {
			if(s[j] < s[(j+i)%n]) {
				break;
			} else if(s[j] > s[(j+i)%n]) {
				return false;
			}
		}
	}
	return true;
}
bool merge(vector<string>& l)
{
	if(l.size() == 1) {
		return false;
	} else {
		bool change = false;
		vector<string> prev = l;
		l.clear();
		vector<string>::iterator it = prev.begin();
		while(it+1 < prev.end()) {
			string s = *it + *(it+1);
			if(isNecklace(s)) {
				l.push_back(s);
				it += 2;
				change = true;
			} else {
				l.push_back(*it);
				it++;
			}
		}
		if(it+1 == prev.end()) {
			l.push_back(*it);
		}
		return change;
	}
}