算法笔记--最小表示法

算法笔记

参考：https://blog.csdn.net/li1615882553/article/details/80136776

https://blog.csdn.net/cillyb/article/details/78058174

考虑每次使两个指针都不向前移动来使得复杂度为O(n)

每次加k+1而不是加k的原因是加k的位置肯定不是最优的，那么就直接跳过了

模板：

const int N = 3e5 + 10;
char s[N];
int Min() {
    int i = 0, j = 1, k = 0, n = strlen(s), d;
    while(i < n && j < n && k < n) {
        d = s[(i+k)%n] - s[(j+k)%n];
        if(!d) k++;
        else {
            if(d > 0) i += k+1;
            else j += k+1;
            if(i == j) j++;
            k = 0;
        }
    }
    return min(i, j);
}

 POJ 1509

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "
";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

const int N = 2e4 + 10;
char s[N];
int get_min() {
    int i = 0, j = 1, k = 0, n = strlen(s), d;
    while(i < n && j < n && k < n) {
        d = s[(i+k)%n] - s[(j+k)%n];
        if(!d) ++k;
        else {
            if(d > 0) i += k+1;
            else j += k+1;
            if(i == j) ++j;
            k = 0;
        }
    }
    return min(i, j);
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s);
        printf("%d
", get_min()+1);
    }
    return 0;
}