题目链接：https://codeforces.com/gym/101667/attachments
题意：现在有一个数列，你需要将前
k
k
k项去除之后剩下的数列形成一个循环数组周期为
p
p
p，平且要求
k
+
p
k+p
k+p最小，当
k
+
p
k+p
k+p相等时
p
p
p最小。
解题心得：找循环节就是
k
m
p
kmp
kmp的应用，只不过这个题需要去除前
k
k
k个，这就可以将数列先翻转，然后再求一个
k
m
p
kmp
kmp，直接找就行了。
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const ll maxn
= 1e6+10;
const ll INF
= 1e17;
int Next
[maxn
], n
, num
[maxn
];
void init() {
scanf("%d", &n
);
for(int i
=n
;i
>=1;i
--) {
scanf("%d", &num
[i
]);
}
}
void cal_next() {
int k
= 0;
for(int i
=2;i
<=n
;i
++) {
while(k
&& num
[k
+1] != num
[i
]) k
= Next
[k
];
if(num
[k
+1] == num
[i
]) k
++;
Next
[i
] = k
;
}
}
int main() {
init();
cal_next();
int ans_p
= 1e7, ans_k
= 1e7;
for(int i
=1;i
<=n
;i
++) {
int len
= i
- Next
[i
], pos
= n
- i
;
if(len
+ pos
< ans_p
+ ans_k
) {
ans_p
= len
;
ans_k
= pos
;
} else if(len
+ pos
== ans_p
+ ans_k
&& ans_p
> len
) {
ans_p
= len
;
ans_k
= pos
;
}
}
printf("%d %d\n", ans_k
, ans_p
);
return 0;
}
