本文共 2205 字，大约阅读时间需要 7 分钟。
题目：
Alice thought out a positive integer x, and x does not have leading zeros. She writes x several times in a line one by one and gets a digits sequence. For example, suppose the number Alice thought out is 231 and she writes it 4 times, then she will get the digits sequence 231231231231. Now Alice just shows you a continuous part of that digits sequence, and could you find out the minimum probable value of x? For example, if Alice showed you 31231, x may be 312, because you will get 312312 if you writes it 2 times, and 31231 is a continuous part of 312312. Obviously x may also be 231, 1231, 31231, 231731, etc. But the minimum probable value of x is 123, write it 3 times and you will see 31231 is a continuous part of 123123123.
The first line has one integer T, means there are T test cases. For each test case, there is only one digits sequence in a line. The number of digits is in range [1, 105]. The size of the input file will not exceed 5MB.
For each test case, print the minimum probable value of x in one line.
477731231401230
71231234010
思路：
首先根据kmp求出字符串的周期，参考
然后字符串最小表示法有个专门的方法，思想和kmp很像
代码：
#include#include using namespace std;char c[200005];int next_[100005];int l;void get_next(char *t, int m, int next[]){ int i = 1, j = 0; next[0] = next[1] = 0; while (i < m) { if (j == 0 || t[i] == t[j])next[++i] = ++j; else j = next[j]; }}int getmin(int n){ int i = 1, j = 2, k = 0; while (i <= n && j <= n && k <= n) { if (c[i] == '0')i++; else if (c[j] == '0')j++; else if (i == j)j++; else if (c[i + k] == c[j + k])k++; else if (c[i + k] > c[j + k])i += k + (!k), k = 0; else j += k + (!k), k = 0; } return (i <= n) ? i : j;}int main(){ int t; scanf("%d", &t); c[0] = '0'; while (t--) { scanf("%s", &c[1]); l = strlen(c + 1); bool flag = true;//全0 for (int i = 1; i <= l; i++)if (c[i] != '0')flag = false; if (flag) { printf("1%s\n", c + 1); continue; } get_next(c, l, next_); int k = next_[l]; while (k && c[l] != c[k])k = next_[k]; l -= k; for (int i = l + 1; i <= l * 2; i++)c[i] = c[i - l]; int key = getmin(l); c[key + l] = '\0'; printf("%s\n", c + key); } return 0;}
转载地址：http://wtlxz.baihongyu.com/