JZOJ 3260【GDOI模拟】Rotate（字符串最小同构）

题解：

第一个问题是如何求出一个字符串最小同构。

高级算法：

把字符串copy一遍接到后边。

如果用倍增法求SA，复杂度$O(nlogn)$ 如果用DC3求SA，复杂度$O(n)$，但是常数巨大。 如果用SAM，时间复杂度$O(n)$，空间复杂度$O(n\ast |str|)$，显然不能接受。

low爆的扫描：

可以看看周源的论文《浅析“最小表示法”思想在字符串循环同构问题中的应用》。

他这个是在两个串上搞事情，实际上并不用，只用求一个串的最小表示开始的位置就行了，写法可以代码。

---

后面的话就是EXKMP的板，正反做两次就行了。

Code：

#include<cstdio> #include<algorithm> #define fo(i, x, y) for(int i = x; i <= y; i ++) #define max(a, b) ((a) > (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b)) #define pc putchar using namespace std; const int N = 1e6 + 5; int n, m, st; char s[N * 2], t[N * 2], S[N]; int calc(char *s, int l) { int i = 1, j = 2, k = 0, t; while(i <= l && j <= l && k <= l) { t = s[i + k] - s[j + k]; if(!t) k ++; else { if(t > 0) i = i + k + 1; else j = j + k + 1; if(i == j) j ++; k = 0; } } return i < j ? i : j; } struct EXKMP { int nt[N * 2], h[N * 2]; void zk() { int a = 2, p = 1; while(p < n && s[p] == s[p + 1]) p ++; nt[1] = n; nt[2] = p - 1; fo(i, 3, n) { if(nt[i - a + 1] >= p - i + 1) { int j = max(0, p - i + 1); while(i + j <= n && s[j + 1] == s[i + j]) j ++; nt[i] = j; a = i; p = i + j - 1; } else nt[i] = nt[i - a + 1]; } } void tk() { int a = 1, p = 0; while(p < n && p < m && s[p + 1] == t[p + 1]) p ++; h[1] = p; fo(i, 2, m) { if(nt[i - a + 1] >= p - i + 1) { int j = max(0, p - i + 1); while(j < n && i + j <= m && s[j + 1] == t[i + j]) j ++; h[i] = j; a = i; p = i + j - 1; } else h[i] = nt[i - a + 1]; // if(i + h[i] - 1 > n) h[i] = m - i + 1; } } } a, b; int ans; int main() { scanf("%d %d", &m, &n); scanf("%s %s", t + 1, s + 1); fo(i, 1, n) s[i + n] = s[i]; fo(i, 1, m) t[i + m] = t[i]; m *= 2; st = calc(s, n); fo(i, st, st + n - 1) S[i - st + 1] = s[i]; fo(i, 1, n) s[i] = S[i]; a.zk(); a.tk(); reverse(s + 1, s + n + 1); reverse(t + 1, t + m + 1); b.zk(); b.tk(); reverse(s + 1, s + n + 1); reverse(t + 1, t + m + 1); fo(i, 1, n) pc(s[i]); pc('\n'); m /= 2; fo(i, 1, m) { if(a.h[i] + b.h[2 * m - n - i + 2] + 1 >= n) { if(!ans) ans = i; if(min(ans, m - ans + 1) > min(i, m - i + 1)) ans = i; } } fo(j, ans, ans + m - 1) pc(t[j]); return 0; }