一个字符串的最小循环表示:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int n;
- int a[600005];
- int min_representation() {
- int i = 0, j = 1, k = 0;
- while(i <n && j < n && k < n) {
- int t = a[(i + k) % n] - a[(j + k) % n];
- if(t == 0)
- k++;
- else {
- if(t> 0)
- i += k + 1;
- else
- j += k + 1;
- if(i == j)
- j++;
- k = 0;
- }
- }
- return min(i, j);
- }
- int main() {
- #ifdef Yinku
- freopen("Yinku.in", "r", stdin);
- #endif // Yinku
- scanf("%d", &n);
- for(int i = 0; i < n; ++i) {
- scanf("%d", &a[i]);
- a[i + n] = a[i];
- }
- int t = min_representation();
- for(int i = 0; i < n; ++i)
- printf("%d%c", a[t + i], "\n"[i==n-1]);
- }
比 SAM 要快很多呢.
来源: http://www.bubuko.com/infodetail-3166237.html