最小表示法.pdf

AcWing 158. 项链

有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！
在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。
达达要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字 0 至 9 来标示。
一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： 0−1−2−3，它的可能的四种表示是 0123、1230、2301、3012。
达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。
也就是说给定两个项链的表示，判断他们是否可能是一条项链。

输入格式

输入文件只有两行，每行一个由字符 0 至 9 构成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

输出格式

如果两个对项链的描述不可能代表同一个项链，那么输出 No，否则的话，第一行输出一个 Yes，第二行输出该项链的字典序最小的表示。
数据范围
设项链的长度为 L，1≤L≤1000000
输入样例：
2234342423
2423223434
输出样例：
Yes
2234342423

  1. import java.util.*;
  3. public class Main {
  4.     static int N = 2000010;
  5.     static char[] a = new char[N], b = new char[N];
  6.     static int n;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  10.         String s = sc.next(), t = sc.next();
  11.         n = s.length();
  12.         for (int i = 0; i < n; i++) {
  13.             char c1 = s.charAt(i), c2 = t.charAt(i);
  14.             a[i] = a[i + n] = c1;
  15.             b[i] = b[i + n] = c2;
  16.         }
  18.         int sa = getMin(a, n), sb = getMin(b, n);
  19.         String ra = new String(a, sa, n), rb = new String(b, sb, n);
  21.         if (ra.equals(rb)) {
  22.             System.out.println("Yes");
  23.             System.out.println(ra);
  24.         } else System.out.println("No");
  25.     }
  27.     static int getMin(char[] a, int n) {
  28.         int i = 0, j = 1;
  29.         while (i < n && j < n) {
  30.             int k = 0;
  31.             while (k < n && a[i + k] == a[j + k]) k++;
  32.             if (k == n) break;
  33.             if (a[i + k] > a[j + k]) i += k + 1;
  34.             else j += k + 1;
  35.             if (i == j) j++;
  36.         }
  37.         return Math.min(i, j);
  38.     }
  39. }

其它例题
leetcode-899. 有序队列
BZOJ 2882 工艺
POJ-1509 Glass Beads
HDU-2609 How many