题目描述

给出一个长度为n 的由小写字母组成的字符串a，设其中第i 个字符为a_i(1\le i\le n)。

设删掉第i 个字符之后得到的字符串为s_i，请按照字典序对s_1,s_2,\cdots,s_n 从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

输入格式

第一行一个整数n。

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

输出格式

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

输入输出样例 #1

输入 #1

7

aabaaab

输出 #1

3 7 4 5 6 1 2

说明/提示

对于所有数据，1\le n\le 10^6。

对于 10% 的数据，1\le n\le 2000；

对于另外 20% 的数据，1\le n\le 10^5且任意两个相邻字符a_i,a_{i+1} 不相等；

对于另外 30% 的数据，1\le n\le 10^5；

对于余下 40% 的数据，无特殊限制。

思路

一、暴力思路

先做一个a[i]，值表示表示扣掉的是第几个字符，初始化为a[i]=i，单独写一个bool cmp(int x,int y)函数对a进行排序，比较两个扣掉的字符集return，最后输出排序过的a，复杂度是排序+字符串遍历，平均 O(n^2\log n)，显然超时。

最坏情况下整串需要遍历

二、优化暴力

考虑在删第一个字符的位置之前一定相等，在删第二个字符的位置之后一定相等，比较的次数减少，但总复杂度不变（应该能多过几个点）。

bool cmp(int x,int y) {
	if(x>y)//保证x小于y，x删去的地方早于y删去的地方 
		return !cmp(y,x);
	for(int i=x+1;i<=y;i++)
		if(s[i]<s[i-1])//s[i]取到的是x串的值，s[i-1]取到的是y串的值
			return 1;
		else if(s[i]>s[i-1])
			return 0;
	return 1;//x串y串相同，x比y小，所以直接返回1
}

30pts

仅遍历[x,y]范围内字符

三、正解

预处理一些操作，可以比较原串和删去一个字符的串在哪里会不同，记录其下标到k[i]中，直接拿来cmp比较，砍到O(n^2)，感觉还可能卡掉（我直接写优化了......这个跳过了），所以还可以优化吗？

然后有脑子的同学就发现了，比较操作实则就比较了s[j]和s[j-1]前后两个值。考虑使用双指针优化，第一个指针i遍历删去字符串的位置，第二个指针j 负责扫第一处两个字符串出现不同的地方，且j是不需要回退重扫的，当i，j相同时，j++以后继续扫。

int j=1;
for(int i=0;i<n;i++) {
	if(i==j)
	j++;
	while(s[j]==s[j-1] and j!=n)
		j++;
	k[i]=j;
}

红色代表删除字符后前移，第一次发现不同的地方在蓝色部分，使标记k[i]=5

cmp函数比较k[x]和k[x]-1的字符。如果 x串 与原串出现不同的地方不在(x,y) ，即k[x]>y，则两串相同，直接选择小的那个return 1。

bool cmp(int x,int y)
{
	if(x>y)
		return !cmp(y,x);
	if(k[x]>y)
		return 1;
	return s[k[x]]<s[k[x]-1];
}

参考程序

#include <bits/stdc++.h>
using namespace std;
int n,a[1145141],k[1145141];
string s;
bool cmp(int x,int y)
{
	if(x>y)
		return !cmp(y,x);
	if(k[x]>y)
		return 1;
	return s[k[x]]<s[k[x]-1];
}
int main()
{
	cin>>n;
	cin>>s;
	for(int i=0;i<n;i++)
		a[i]=i;
	int j=1;
	for(int i=0;i<n;i++) {
		if(i==j)
			j++;
		while(s[j]==s[j-1] and j!=n)
			j++;
		k[i]=j;
		//cout<<k[i]<<" ";
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++) {
		cout<<a[i]+1<<" ";//因为从1数起遍历不方便所以我先从0数起，输出时+1
	}
	return 0; 
}

非常好的字符串题，完结撒花。