1550: AA

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?125??Solved:?35
[Submit][Status][Web Board]

Description

?其實第一次聽說要出題目我是拒絕的，因為，你不能讓我出，我就馬上去出，我要試一下，因為我不愿意出完了以后再加一些案例上去，然后題目duang的一下就被AC了。現在要求對字符串進行環狀左移操作，每次向左移動一個位置。例如：對duang進行操作，得到的全部字符串為：

duang

uangd

angdu

ngdua

gduan

輸出得到最小字典序的字符串的最小移動次數。

Input

輸入一個數T(1<=T<=100),表示接下來有T行字符串；輸入字符串S，S的長度為L（5<=l<=100000）。

Output

輸出一個數字，表示為得到最小字典序的字符串的最小移動次數。

Sample Input

2

baabaa

alabala

Sample Output

1

6

解析：這道題考的就是字符串的最小表示法。起先我做的是直接求，不是超時就是超內存。這讓我學到了很多，有時候我做題目并不是為AC，而是去學更多的東西，雖然錯了很多次，但是你會知道是由于什么錯了，可以學更多。

最小表示法------詳細看博客

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}int _find(string str) {int i = 0;int j = 1;int k = 0;int len = str.size();while(i<len && j<len && k<len ){int t = str[(i+k)%len] - str[(j+k)%len];if(t == 0)k++;else{if(t>0)i+=(k+1);elsej+=(k+1);if(i == j)j++;k=0;}}return i<j?i:j; } int main() {int T;scanf("%d",&T);while(T--){string s;cin>>s;int cnt=_find(s);printf("%d\n",cnt);}return 0; }

?

?

總結

以上是生活随笔為你收集整理的zcmu1550（字符串最小表示法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。