bzoj 2176 最小表示

2022-12-04 18:30:15

2176: Strange string

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 419 Solved: 174
[Submit][Status][Discuss]

Description

给定一个字符串S = {S₁, S₂, S₃ … S_n}, 如果在串SS中, 子串T(|T| = n)为所有长度为n的SS的字串中最小的(字符串的比较), 则称T为”奇怪的字串”. 你的任务就是找出这个字符串.

Input

读入两行, 第一行为n, 第二行为字符串S.

Output

将”奇怪的字串” T输出输入样例

Sample Input

10
asdfasdfas

Sample Output

asasdfasdf

HINT

数据范围

对于100%的数据, 保证n≤10000000;

给定的字符串中的字符保证在#33 ~ #254之间.

题解：最小表示法。

 #pragma GCC optimize(2)

 #pragma G++ optimize(2)

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #define N 10000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 unsigned char a[N*];

 int solve()

 {

     int i=,j=;

     while(i<=n&&j<=n)

     {

         int k=;while(a[i+k]==a[j+k]&&k<=n-)k++;

         if(k==n)break;

         else if (a[i+k]<a[j+k])j=max(i+,j+k+);

         else i=max(j+,i+k+);

     }

     return min(i,j);

 }

 int main()

 {

     n=read();

     scanf("%s",a+);

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

         a[i+n]=a[i];

     int st=solve();

     for (int i=st;i<=st+n-;i++)

         putchar(a[i]);

 }

码农公寓