名称：字符串
来源：2019年陕西省选

题目内容

传送门

• 洛谷(p5392)

  题目描述

  给出一个长度为$n$的由小写字母组成的字符串$a$，设其中第$i$个字符为$a_i(1≤i≤n)$。
  设删掉第$i$个字符之后得到的字符串为$s_i$，请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

  输入&&输出

  格式

  输入

  第一行一个整数$n$。
  第二行一个长为$n$的由小写字母组成的字符串$a$。

  输出

  输出一行$n$个整数￥k_1,k_2,……,k_n$，用空格隔开。表示$s_{k_1}<s_{k_2}<……<s_{k_n}$。

  样例

  输入

7 aabaaab

输出

3 7 4 5 6 1 2

数据范围

对于所有数据，$1leq nleq10^6$。
对于10%的数据，$1leq nleq2000$。
对于另外20%的数据，$1leq nleq10^5$。且任意两个相邻字符$a_i,a_{i+1}$不相等；
对于另外30%的数据，$1leq nleq10^5$。
对于余下40%的数据，无特殊限制。

提示

本题不需要sa或者sam等高级算法。

题解

10分

暴力构造出$s$，再用快速排序进行排序。时间复杂度为$o(n^2log(n))$，在$nleq2000$的数据下跑得过。

30分

注意到：其中20%的数据没相邻两个字符不相等。

引理
当其任意两个字符不相等时，$s_i$和$s_j(i<j)$的大小关系实际上就是$a_{i+1}$与$a_i$的大小关系。
证明：由题意得。
$$
s_i[1……i-1]=a[1……i-1]=s_j[1……i-1]
s_i[j……n-1]=a[j+1……n]=s_j[j……n-1]
$$
重点在于比较$s_i[i……j-1]$和$s_j[i……j-1]$的大小关系。
$s_i[i……j-1]$正对应$a[i+1……j]$；
$s_j[i……j-1]$正对应$a[i……j-1]$；
而$a[i+1]!=a[i]$，故二者的大小关系可以确定。

于是，我们可以开一个双端队列。逆序处理整个字符串。
当我们发现$a[i+1]<a[i]$时，则说明$s_i$比后面的（即已经被处理过放进双端队列里的）都要小，就把数字$i$放在双端队列的前面；否则说明$s_i$比后面的都要大，就把它放在双端队列的后面。

start=>start: 开始处理状态i cmp=>condition: a[i+1]<a[i] front=>operation: 将i插在双端队列前面。 back=>operation: 将i插在双端队列后面 end=>end: 进入下一轮操作  start->cmp cmp(yes)->front->end cmp(no)->back->end

最后我们按顺序将双端队列每一个位置上的数字。

100分

那么，我们如何拿到100分呢？？？
实际上，我们只需要将原来30分的做法进行扩展，或者说将所有情况转换为两两相邻字符不相等的情况就行。

引理
当$a[i]=a[i+1]$时，$s[i]=s[i+1]$
证明略

由此，我们就可以将字符串连续相同的一段进行压缩，其中每一个字母都代表着原字符串的一段区间。
例如$"bbbcaa"$压缩成$"bca"$，并且处理出来如下数据：
|字母|开始位置|结束位置|
|:-|-|-|
|b|1|3|
|c|4|4|
|a|5|6|
将压缩后的串排序得$3quad1quad2$。
将原来处理出来的数据带入得$(5quad6)(1quad2quad3)(4)$。

//c++ #include<iostream> #include<stdio.h> #include<string> #include<deque> using namespace std; const int nn=1000001; inline void output(long long o); int start[nn],final[nn]; inline long long input(); string a; deque<int>k; int main() {     int n=input(),size=0;     cin>>a;     for(int i=0,prev=0;i<n;i++)     {         prev=i;         while(a[i]==a[i+1]&&i<n)i++;         a[size]=a[i],start[size]=prev+1,final[size++]=i+1;     }     for(int i=size-1;i>=0;i--)     if(a[i+1]<a[i])k.push_front(i);     else k.push_back(i);     for(;k.front()!=k.back();k.pop_front())     for(int i=start[k.front()],f=final[k.front()];i<=f;i++)output(i),putchar(' ');     for(int i=start[k.front()],f=final[k.front()];i<f;i++)output(i),putchar(' ');     output(final[k.front()]),putchar('n');     return 0; } inline void output(long long o) {     if(o<0)putchar('-'),o=-o;     if(o>=10)output(o/10);     putchar(o%10^'0'); } inline long long input() {     bool positive=true;     char now=getchar();     long long i=0;     for(;!isdigit(now);now=getchar())     if(now=='-')positive=!positive;     for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');     return positive?i:-i; }