当前位置 博文首页 > 可惜浅灰的博客：环形字符串处理：UVA1584 环状序列
题目描述：
长度为n?的环状串有n?种表示法，分别为从某个位置开始顺时针得到的。在环状串的所有表示法中，字典序最小的称为“最小表示”。
输入一个长度为n?的环状DNA串（只包含A?，C?，G?，T?这四种字符）的一种表示法，你的任务是输出该环状串的最小表示。
解题思路：
对于环形序列有两种处理方式：
? ? 方式1：把序列s复制一份，与原序列首尾相连，拉长为一个直线串，如 环状序列ATC -> 直线序列ATCATC；或者也可以去复制一份去掉尾元素后，与原序列首尾相连，如 环状序列 ATC - > 直线序列ATCAT（因为第一个子串会与最后一个子串重复）；
? ? 方式2：下标取余，i % (len - 1)
1、将输入的字符串s复制后拼接成直线长串，记录原字符串长度len，并定义最小字符串mins；
2、定义循环变量i，从头开始遍历，直至原字符串的尾部；取子串，从i处开始，长度为len，若小于mins则更新mins。
解题思路2：
1、将输入的字符串s复制后拼接成直线长串，记录原字符串长度len，并定义最小字符串开始时的位置min；
2、定义循环变量i，从头开始遍历，直至原字符串的尾部；
3、i和min同时开始向后比较字符，直到取到len个为止，如果出现字符不相等，且s[i+t] < s[min + t]，更新min。
4、遍历字符串后从min处取子串，截取长度为len。
代码实现：
#include <iostream>
using namespace std;
#include <string>
string s;
bool Rev(const int& p, const int& q, const int& len)
{
for (int i = 0; i < len; i++)
{
if (s[p + i] != s[q + i])
{
return s[p + i] > s[q + i];
}
}
return 0;
}
int main()
{
while (cin >> s)
{
string mins = s, temp = s;
int len = s.size();
s += s;
#if 0
//方法1
for (int i = 1; i < len; i++)
{
temp = s.substr(i, len);
if (temp < mins)
{
mins = temp;
}
}
cout << mins;
#else
//方法2
int min = 0;
for (int i = 1; i < len; i++)
{
if (Rev(min, i, len))
{
min = i;
}
else
{
continue;
}
}
mins = s.substr(min, len);
cout << mins << endl;
#endif
}
return 0;