字符串（二）

Posted on | In | | Visitors:
Words count in article: 2.9k | Reading time ≈ 13

8202bbc4fd236726eab9a919e9f34a9d.jpg

马拉车（Manacher）与回文自动机（PAM）

回文串

反转串$R(S)$：一个字符串$S=S[1]S[2]…S[n]$，其反转串$R(S)=S[n]…S[2]S[1]$
回文串：满足$S=R(S)$的字符串
回文中心：奇数长度的回文串为$\dfrac{n+1}{2}$，偶数长度的回文串为$\dfrac{n}{2}$和$\dfrac{n}{2}+1$之间
回文半径：回文中心到左右端点的距离。
回文与Border：回文串$S$的回文前（后）缀等价于其Border。

Manacher

首先为了避免讨论奇偶长度，将字符串$S$的首尾以及相邻两字符之间插入一个$S$字符集以外的字符$*$，得到
$S^{*}=*S[1]*S[2]*…*S[n]*$。
在$S^*$上重新定义极长回文串为长度为奇数且最大，且满足$S=R(S)$的字符串。

定义$Len[i]$为以$i$为回文中心的最大回文半径，为Manacher的求解目标。
定义最右回文串$P$为所有已求得的回文串中，右端点最大的回文串。
设已经求出$Len[1],Len[2],…,Len[i-1]$，此时的$P$为$S^*[L,R]$，回文中心为$p$，对$i$和$p,R$的关系进行讨论：

  • $i>R$，则从$i$处向左右暴力扩展，得到回文半径$Len[i]$以及新的$P$；
  • $i\le R$，这就意味着$i\in(p,R]$，因此在$[L,p)$可以找到$i$的对称位置$j=2p-i$，而$Len[j]$是已经求过的，所以继续根据$Len[j]$的情况讨论：
    • $Len[j]< j-L+1$，说明以$j$为回文中心的极长回文串并没有超出$P$的范围，所以$Len[i]=Len[j]$；
    • $Len[j]\ge j-L+1$，说明以$j$为回文中心的极长回文串可能会超出$P$的范围，而根据$p$对称过去的部分在$R$后面，并没有考察过，因此$Len[i]$首先继承了$Len[j]$中不超过$P$的范围，即$j-L+1$这部分，然后从这个状态继续向左右暴力扩展。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Manacher(char s[], int len[], int n) {
    for (int i = n - 1; ~i; --i)s[i + 1 << 1] = '*', s[i << 1 | 1] = s[i];
    s[0] = '*';
    n = n << 1 | 1;
    len[0] = 1;
    int L = 0, R = 0, p = 0;
    for (int i = 1; i < n; ++i) {
        if (i > R) {
            len[i] = 0;
            while (i + len[i] < n && i - len[i] >= 0 && s[i + len[i]] == s[i - len[i]])
                ++len[i];
            p = i, L = i - len[i] + 1, R = i + len[i] - 1;
        }
        else {
            int j = (p << 1) - i;
            if (len[j] < j - L + 1)len[i] = len[j];
            else {
                len[i] = j - L + 1;
                while (i + len[i] < n && i - len[i] >= 0 && s[i + len[i]] == s[i - len[i]])
                    ++len[i];
                p = i, L = i - len[i] + 1, R = i + len[i] - 1;
            }
        }
    }
}

复杂度分析

对于$i>R$和$Len[j]\ge j-L+1$的情况，暴力扩展操作每进行一次都会使得$R$增加，而$R$的最大值为$\left|S^*\right|$，因此总复杂度为$O(\left|S^*\right|)$。

用途

首先是可以求$Len[i]$，即每个位置的回文半径。
可以求本质不同的回文子串的数量，因为本质不同的回文子串只会在$R$增大的时候增加，所以可以得到一个性质：
对于长度为$n$的字符串$S$，其本质不同的回文子串个数最多只有$n$个。

回文自动机（PAM）

PAM的结构与ACAM类似。
PAM的节点最多$n$个，每个节点表示了一种回文串。用$S(u)$表示节点$u$所代表的回文串。$len[u]=\left|S(u)\right|$
后继边：每个后继边上有一个字母$ch$。用$trans(u,ch)=v$表示$u$节点有后继边$ch$指向$v$节点，则有$S(v)=chS(u)ch$，且$len[v]=len[u]+2$。
失配边：每个节点都有一个失配边，用$fail[u]=v$，表示$u$节点的失配边指向了$v$节点。则有$S(v)$是$S(u)$的最大Border，即最长回文后缀。

需要注意的是，奇数与偶数的回文串是有差别的，因此我们的PAM中不能只有一个根，应该有表示奇数和偶数长度的两个根，偶数根的$len$为$0$，奇数根的$len$为$-1$，且这两个根的$fail$指针互相指向对方。
那么接下来依次考察$S$的每个字符来构造PAM，设当前我们所在的节点是$now$，那么我们就去考察$S[i]$与$S[i-len[now]-1]$是否相等，如果不相等就跳到$fail[now]$继续比较，直到比较成功，这里就会发现当除了根都无法匹配的时候，一定会在奇数根处匹配成功，这是符合要求的。
若在某处匹配成功，且此时$now$并没有$S[i]$的后继边，那么就需要添加一个新的节点。新的节点就需要求$fail$，从新节点的父节点处向上搜整条$fail$链，找到第一个匹配的位置，即为所求的$fail$链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct PAM {
    int c[N][26], fail[N], tot, rt0, rt1, len[N];
    vector<int>to[N];
    void build(char s[], int n) {
        rt0 = ++tot, rt1 = ++tot;
        len[rt0] = 0, len[rt1] = -1;
        fail[rt0] = rt1;
        fail[rt1] = rt0;
        int now = rt0;
        for (int i = 1; i <= n; ++i) {
            int nt = s[i] - 'a';
            while (i - len[now] - 1 < 0 || s[i] != s[i - len[now] - 1])
                now = fail[now];
            if (!c[now][nt]) {
                c[now][nt] = ++tot;
                len[tot] = len[now] + 2;
                int x = fail[now];
                while (i - len[x] - 1 < 0 || s[i] != s[i - len[x] - 1])
                    x = fail[x];
                if (tot != c[x][nt])fail[tot] = c[x][nt], to[c[x][nt]].push_back(tot);
                else fail[tot] = rt0, to[rt0].push_back(tot);
            }
            now = c[now][nt];
        }
    }
}A;

PAM Series

前面提到了一个性质：回文串的回文后缀就等价于回文串的border。
所以Border Series运用到PAM上，就有了PAM Series，即：某个回文串的回文后缀最多可能有$n$个，但是将这些回文后缀按长度排序，可以构成$O(\log n)$个等差数列。

后缀数组（SA）

首先需要了解几个字符串中的基本定义：

  • 子串：字符串s中任意截取的一段字符串t称t为s的子串
  • 后缀：字符串s中从任一位置到字符串末尾的子串称为后缀，记为suf(i)
  • 后缀数组：将s的所有后缀按照字典序进行排序，后缀对应的下标组成后缀数组，记sa[i]表示排名为i的后缀起始位置，rk[i]表示起始位置为i的后缀排名

SA求法

这里给出一种常用解法。

基本思想：我们通过倍增的思想，对每个位置以长度为1的子串开始排序，每次将排序的长度翻倍，这样的话就能利用上一次排序的结果通过$\log n$次双关键字排序得到新的排序结果，而这里的排序我们选择基数排序来降低复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void radix_sort() {
	memset(tong, 0, sizeof(int) * (m + 1));
	//b存储第一关键字，其内顺序由第二关键字决定
	for (int i = 1; i <= n; ++i)++tong[rk[b[i]]];
	for (int i = 1; i <= m; ++i)tong[i] += tong[i - 1];
	for (int i = n; i; --i)sa[tong[rk[b[i]]]--] = b[i];
}
void getsa() {
	m = 27;
	for (int i = 1; i <= n; ++i)
		b[i] = i, rk[i] = s[i] - 'a' + 1;
	radix_sort();
	for (int k = 1; k <= n; k <<= 1) {
		int tot = 0;
		for (int i = n - k + 1; i <= n; ++i)b[++tot] = i;//没有第二关键字的排名靠前
		for (int i = 1; i <= n; ++i)
			if (sa[i] > k)//枚举第二关键字
				b[++tot] = sa[i] - k;//sa[i] - k是第一关键字
		radix_sort();//求出sa
		swap(b, rk);//b是旧的rk，以此计算新的rk存储在rk中
		rk[sa[tot = 1]] = 1;
		for (int i = 2; i <= n; ++i)
			if (b[sa[i]] == b[sa[i - 1]] && (sa[i] + k <= n ? b[sa[i] + k] : -1) == (sa[i - 1] + k <= n ? b[sa[i - 1] + k] : -1))
                rk[sa[i]] = tot;//两个关键字都与前一个相同，排名也相同
			else rk[sa[i]] = ++tot;
		if (tot == n)break;
		m = tot;
	}
}

LCP求法

后缀数组最重要的作用就是可以求LCP
LCP，即最长公共前缀，也就是两个字符串的前缀中相同且最长的子串长度。
在这里，我们定义LCP(i,j)为suf(sa[i])和suf(sa[j])的LCP，即排名分别为i和j的两个后缀的LCP。
显然我们有：

  • $LCP(i,j)=LCP(j,i)$
  • $LCP(i,i)=n-sa[i]+1$

接下来就需要证明几个重要的定理

LCP Lemma

设$x=suf(sa[i]),y=suf(sa[j]),z=suf(sa[k]),p=min(LCP(i,j),LCP(j,k))$
显然x与y的前p个字符相等，y与z的前p个字符相等，因此x与z的前p个字符相等，即$LCP(i,k)\ge p$
j在i和k之间，根据字典序，LCP(i,j)与LCP(j,k)都大于等于LCP(i,k)，因此$LCP(i,k)\le p$
综上，$LCP(i,k)=p=min(LCP(i,j),LCP(j,k))$

LCP Theorem

根据LCP Lemma，我们不难得出

Height数组

height数组是求LCP中最重要的一环。
我们定义height[i]=LCP(i,i-1)，为了描述方便，设h[i]=height[rk[i]]则有

我们设k=sa[rk[i-1]-1]，显然LCP(rk[i-1],rk[k])=h[i-1]
现在我们来看看suf(k+1)与suf(i):

  1. $s[k]\not=s[i-1]$
    此时h[i-1]=0，LCP Theorem显然成立
  2. $s[k]=s[i-1]$
    此时suf(i)是suf(i-1)去掉首字符得到的，suf(k+1)是suf(k)去掉首字符得到的，因此suf(i)和suf(k+1)之间的排名关系与suf(i-1)和suf(k)之间的排名关系相同，所以rk[k+1]< rk[i]，而且，LCP(rk[k+1],rk[i])=LCP(rk[k],rk[i-1])-1=h[i-1]-1
    根据定义，h[i]=LCP(rk[i],rk[i]-1)
    接下来只要证明$\max\{LCP(rk[i], j)|j< rk[i]\}=LCP(rk[i],rk[i]-1)$
    又因为rk[k+1]<=rk[i]-1，就可得出h[i]>=LCP(rk[k+1],rk[i])=h[i-1]-1
    而这个证明非常简单，根据字典序，suf(sa[j])的前h[i]个字符只能是suf(sa[rk[i]-1])的前h[i]个字符变小形成，这就保证了j减小的过程中LCP(rk[i],j)不会变大。

求LCP

有了上面的性质和定理，我们就可以在线性复杂度内求出height数组

1
2
3
4
5
6
7
8
9
10
11
12
void getheight() {
	int k = 0;
	for (int i = 1; i <= n; ++i)rk[sa[i]] = i;
	for (int i = 1; i <= n; ++i) {
		//这里i枚举的是位置而不是排名
		if (rk[i] == 1)continue;
		int j = sa[rk[i] - 1];
		if (k)--k;//h[i]>=h[i-1]-1，因此从h[i-1]-1开始检验
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k])++k;//直接找
		height[rk[i]] = k;
	}
}

根据LCP Theorem和height的定义，$LCP(i,j)=\min\{height[k]|i<k\le j\}$
我们用ST表来维护height的区间最小值，即可做到O(1)查询LCP

1
2
3
4
5
6
7
8
9
10
11
12
13
int LCP(int l, int r) {//l和r都是rk值
	if (l == r)return n - sa[l] + 1;
	if (l > r)swap(l, r);
	++l;
	int k = r - l + 1;
	return min(ST[l][k], ST[r - (1 << k) + 1][k]);
}
void init(int n) {
	for (int i = 1; i <= n; ++i)ST[i][0] = height[i];
	for (int j = 1; (1 << j) <= n; ++j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++i)
			ST[i][j] = min(ST[i][j - 1], ST[i + (1 << j - 1)][j - 1]);
}