UVA 1314 最小表示法

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36117

题意：给定长度为n的字符串，求一个起点使字符串从该起点起的字符串字典序最小

思路：最小表示法模板题

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int MAXN =  + ;

typedef long long int LL;

#define INF 0x3f3f3f3f

int MinRepresentation(char *s){

    int i = , j = , k = , l = strlen(s);

    while (i < l&&j < l&&k < l){

        int li, lj;

        li = (i + k) >= l ? i + k - l : i + k;

        lj = (j + k) >= l ? j + k - l : j + k;

        if (s[li] == s[lj]){

            k++;

        }

        else{

            if (s[li]>s[lj]){

                i = i + k + ;

            }

            else{

                j = j + k + ;

            }

            if (i == j){

                j++;

            }

            k = ;

        }

    }

    return i < j ? i : j;

}

char str[MAXN];

int main()

{

    int n,t;

    scanf("%d", &t);

    while (t--){

        scanf("%d", &n);

        scanf("%s", str);

        printf("%d\n", MinRepresentation(str));

    }

    return ;

}