https://www.51nod.com/Challenge/Problem.html#!#problemId=1335
和字典序有關的題 要麼是字元串題 要麼就是DP或者貪心亂搞
找一個最小的i作為x 滿足a[i]>min(a[j]) i+1<=j<=n-1 因為字典序和二進制串一樣 都是高位決定一切
然找出所有k 滿足a[k]==min(a[j]) i+1<=j,k<=n-1 一位一位比出個字典序最小或者y最小的即可
最後注意向兩邊拓展一下xy
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=3e3+10;
vector <int> pre;
int ptr[maxn],book[maxn];
int n;
char ch[maxn];
int main()
{
int t,i,j,x,y;
char minn;
scanf("%d",&t);
while(t--){
scanf("%s",ch);
n=strlen(ch),x=3000,y=3000;
for(i=0;i<n;i++){
minn='z'+1;
for(j=i+1;j<n;j++){
minn=min(minn,ch[j]);
}
if(minn>=ch[i]) continue;
pre.clear();
for(j=i+1;j<n;j++){
if(ch[j]==minn) pre.pb(j);
}
if(pre.size()>0){
x=i;
break;
}
}
for(i=0;i<pre.size();i++){
ptr[i]=pre[i],book[i]=0;
}
for(i=0;i<n-x;i++){
minn='z'+1;
for(j=0;j<pre.size();j++){
if(book[j]) continue;
minn=min(minn,ch[ptr[j]]);
}
for(j=0;j<pre.size();j++){
if(book[j]) continue;
if(ch[ptr[j]]!=minn) book[j]=1;
}
for(j=0;j<pre.size();j++){
if(ptr[j]<=pre[j]){
ptr[j]--;
if(ptr[j]<x) ptr[j]=pre[j]+1;
}
else ptr[j]++;
}
}
for(i=0;i<pre.size();i++){
if(!book[i]) y=min(y,pre[i]);
}
if(x==3000) printf("0 0\n");
else{
while(0<=x-1&&y+1<n&&ch[x-1]==ch[y+1]) x--,y++;
printf("%d %d\n",x,y);
}
}
return 0;
}