题解：P10476 Necklace

· · 题解

前言
这道题其实是老师上课的时候讲的思路。过了一百万个世纪以后由于我还是太垃圾了，还是觉得本题思路不太好理解，所以赶来写了个题解，可能图画的不怎么好，讲解可能也没这么清楚，请谅解。

题目大意
给定两个字符串，判断两个字符串是否同构，如果是就输出字符串的最小表示法。

做法详解
首先，我们确定了本题其实就是字符串的同构问题。那么什么叫做同构呢？通俗易懂的说就是像题目中说的那样，把一个字符串顺时针（当然逆时针也可以）写到环上面，则无论从哪一个地方断开按照原顺序读，这两个字符串在按照同一顺序写在环上面以后是一样的。具体见下图：

那么反过来，如果两个字符串按照顺时针填到两个环上面，这两个环经过旋转后相同，那么就说这两个字符串同构。
那么，我们就可以得出一种做法：先将其中一个字符串破环为链（就是将原字符串在后面复制一遍，这样可以做到以每一个点为起点往后扫描的字符串都可以在这个字符串中顺序找到）再事先开一个存储答案的字符串存储最小的字典序字符串，接着枚举刚才破环为链的字符串的所有表示方法。如果其中一个表示法和另一个字符串相等，就输出刚才的答案字符串。可是显然，设原字符串长度是 L，则这种方法的时间复杂度是 O(L ^ 2) 级别的，在 1 \le L \le 10 ^ 6 的情况下会超时。所以我们需要找更优的方法。
那么我们可以想一想：如果两个字符串同构，他们不管怎么表示，一定有一个什么东西是相同的呢？没错，就是最小表示法。顾名思义，就是在这个字符串所有表示法中字典序最小的那一个。那么这个问题就瞬间转化成了一个求字符串的最小表示法的问题。
现在问题就在于怎么求了。暴力枚举是个不错的选择我们显然不能暴力枚举，那么这时候就要用到双指针了。具体操作如下:

  1. 我们需要两个指针，在操作中需要保证其中的一个指针是目前扫描到所有字符串中最小的，我们把它称为答案指针。
  2. 将一个指针赋成 1，另一个赋成 2。
  3. 进入循环，每一次向后截取，如果当前两个位置相同，则继续，否则跳出。注意：这里最多取 L 个位置。
  4. 对于每一次截取完成之后，如果此时当前非答案指针所代表的字符串更优，交换答案指针和非答案指针，否则不交换。然后将非答案指针设成刚才更劣字符串扫到最后一个位置的后面一个位置。为什么呢？我们看这个例子：

    我们假设答案指针 i 指在前面，非答案指针 j 指在后面，现在扫的字符串长度 k = 5，那么对于每一个字符串的开始位置 j+h(0 \le h < k)，都肯定能会有 i+h，使得以 i+h 作为开始位置的字符串比以 j+h 作为开始位置的字符串更优。例如图中当 h = 2 时就是如此。故可以直接将 j 挪到 j+k 的位置（注意字符串长度是 k，实际上最后一个位置是 j+k-1 哦）。

  5. 出循环之后，最小表示法字符串即是从答案指针开始向后取一个长度为 L 的字符串。
    我们可以分析一下这种做法的时间复杂度，因为指针不可能回退，所以时间复杂度是 O(L) 级别的。

    代码

    #include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LONG_LONG_MAX
#define INT_MIN LONG_LONG_MIN
string a,b,ansa,ansb;
int n;
string minstring(string s) {
int i,k;
i = 1;
for(int j = 2; i<=n && j<=n;) { //不是i(j)<=2*n，因为要给后面留n个空间截取字符串
    int k;
    for(k = 0; k<n && s[i+k] == s[j+k]; k++); //向后找
    if(s[i+k]>s[j+k]) {
        swap(i,j);
    }
    j = j+k+1;
    if(i == j) {
        j++;
    }
}
return s.substr(i,n);//意思是从i开始向后截取，取一个长度为n的字符串 
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>a>>b;
n = a.size();
a = " "+a+a;
b = " "+b+b;
ansa = minstring(a);
ansb = minstring(b);
if(ansa == ansb) {
    cout<<"Yes\n"<<ansa;
} else {
    cout<<"No";
}
cout<<"\n";
return 0;
}