暑假训练Round1——G: Hkhv的水题之二（字符串的最小表示）

Problem 1057: Hkhv的水题之二

Time Limits: 1000 MS Memory Limits: 65536 KB

64-bit interger IO format: %lld Java class name: Main

Description

杨神喜欢字符串，于是他写程序随机生成了n个长度不大于100的字符串。但是他认为这里面有一些字符串是一样的。比如，abcd,bcda,cdab,dabc这4个他认为就是一样的.
因此，杨神想知道，这些随机生成的字符串有几个是不同的，并且要输出这些字符串。杨神还有强迫症，输出的时候要按字典序从小到大排，字符串也要是最小的。
比如cdba要输出acdb.

Input

测试数据有多组。第一行输入n ( 1 <= n <= 10000) 接下来n行输入只有小写字母组成的字符串

Output

第一行为多少个字符串是不同的，接下来输出这些字符串，并且按字典序从小到大排。

Sample Input

5

asdfadf

abcd

bcda

cdab

dabc

Output for Sample Input

2

abcd

adfasdf

一开场发现这道题做过类似的，大水题，一提交，超时，关掉同步，WA，然后就开始无限WA了……弄了很久想不明白，问了学长发现是自己以前学这个的时候看的模版是错误的，最杯具的是这个模版一直用到这个比赛之前做过的题都是可以AC的……还好这次数据够强WA了……之后去学了下正确的写法，有空把会以前的题解代码都改成正确的……希望不会有人再被误导了

代码：

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define MM(x,y) memset(x,y,sizeof(x))

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

string minp(string s)

{

	int i=0,j=1,k=0,len=s.size(),t;

	while (i<len&&j<len&&k<len)

	{

		t=s[(i+k)%len]-s[(j+k)%len];

		if(!t)

			k++;

		else

		{

			if(t>0)

				i+=k+1;

			else

				j+=k+1;

			k=0;

			if(i==j)

				j++;

		}

	}

	s+=s;

	return s.substr(min(i,j),len);

}

int main(void)

{

	ios::sync_with_stdio(false);

	cin.tie(0);

	string s;

	int n,i,j;

	set<string>pos;

	set<string>::iterator it;

	while (cin>>n)

	{

		pos.clear();

		for (i=0; i<n; i++)

		{

			cin>>s;

			pos.insert(minp(s));

		}

		cout<<pos.size()<<endl;

		for (it=pos.begin(); it!=pos.end(); it++)

			cout<<*it<<endl;

	}

	return 0;

}

巴特西