首页 > 代码库 > UVA 1584 环状序列
UVA 1584 环状序列
题意:
给定一个环状字符串,输出字典序最小的线装字符串。
分析:
我一开始是将原字符串*2去模拟环,然后分别截取以字符串不同字母为首的子串,然后用sort去排序输出最小的串,复杂度为O(n^2 + nlogn)吧。
然后看了紫书的题解,用了一个函数去枚举比较每一个字母为开头的子串和预估答案的子串的字符串字典序大小,枚举串的某一个字母的使整个串字符串小于另一个串(他们长度都是一样的,只要其中一个小,那么整个就会小,因为字典序是取决前面的字母的)就立刻更新ans,然后他用的是下标mod长度,最坏复杂度为O(n^2)。
// UVa1584(LA3225) Circular Sequence
// Rujia Liu
#include<stdio.h>
#include<string.h>
#define maxn 105
// 环状串s的表示法p是否比表示法q的字典序小
int less(const char* s, int p, int q) {
int n = strlen(s);
for(int i = 0; i < n; i++)
if(s[(p+i)%n] != s[(q+i)%n])
return s[(p+i)%n] < s[(q+i)%n];//如果小于就reture true;
return 0; // 相等就不更新
}
int main() {
int T;
char s[maxn];
scanf("%d", &T);
while(T--) {
scanf("%s", s);
int ans = 0;
int n = strlen(s);
for(int i = 1; i < n; i++)
if(less(s, i, ans)) ans = i;
for(int i = 0; i < n; i++)
putchar(s[(i+ans)%n]);
putchar(‘\n‘);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
string a;
cin>>a;
int length = a.size();
a = a + a;
string sub[105];
for(int i = 0; i < length; i++)
{
sub[i] = a.substr(i,length);
//cout<<sub[i]<<endl;
}
sort(sub,sub+length);
cout<<sub[0]<<endl;
}
}
UVA 1584 环状序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。