String Modification Problem solving report

label ： character string Looking for a regular simulation

Topic link

The question ：

Given a length of n（1≤n≤5000 ） String , Traverse from the beginning , For each k Flip the length subsequence , Find the one with the smallest dictionary order and k Value , If there are multiple dictionaries with the smallest order , requirement k Minimum .

Their thinking

First, find out the rules through simulation

Set string 12345;

k=1 12345

k=2 2345 1

k=3 345 21

k=4 45 123

k=5 5 4321

You can find If we divide strings into pre sequence and post sequence , The inverted sequence will be the exchange position of the front and rear sequences , According to the current example, the original pre sequence follows k And decide whether to flip , In addition, the length of the previous sequence can be determined to be k-1.

Set string 123456

k=3 3456 12

k=4 456 321

From these two examples, we can find ： Whether the previous sequence is reversed is determined by k And string length n Of or related to .

Code implementation

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	string s,ans;
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		cin>>s;
		ans=s;
		int k=1;
		for(int i=2;i<=n;i++){
			string s1,s2,s3;
			s1=s.substr(0,i-1);
			s2=s.substr(i-1);// from i-1 Until the position of is taken back 
			if((n-i)%2==0) reverse(s1.begin(),s1.end());
			s3=s2+s1;
			if(s3<ans){
				k=i;
				ans=s3;
			}
		}
		cout<<ans<<endl;
		cout<<k<<endl;
	}
}