lcp: longest common prefix
lcp[i][j]为: s[i, i+1, …, n] 和 s[j, j+1, …, n] 这两个串,的最长公共前缀 的长度。
即s.substr(i, lcp[i][j]) = s.substr(j, lcp[i][j])
前缀是一个连续的子段!!!
_s : 1 2 3 4 1 2 3 3
lcp: 0 1 2 3 4 5 6 7
那么,lcp[0][4] = 3。 表示: 123
这个连续子段。
即需求是: 对于一个字符串s,给定一个i 和 j
问,s[i, …, n] 和 s[j, …, n] 这两个子段,的最长公共前缀(一个以s[i]开头,一个以s[j]开头)
lcp[i][j] 便是答案。
s: a a a a a
i j
s[i,...]: a a a a a
s[j,...]: a a a a
两者从左侧开头,按位的比较。 lcp为:a a a a,即长度为4
当i == j时,此时一眼可以看出,lcp是:s[i, …, n],不用借用lcp算法。
当i != j时, lcp[i][j] = lcp[j][i]
即,lcp算法 只需要处理: i < j 的情况即可。
可以发现,这可以用dp解决。
从上面样例可以看出,lcp[i][j] (i < j), 以s[i]开头的lcp 他可能会包含s[j]元素!!
void build_lcp( const string & _s ){
int n = _s.size();
for(int i = n - 2; i >= 0; --i){
lcp[ i ][ n - 1 ] = ( _s[i] == _s[n - 1] );
}
for(int i = n - 3; i >= 0; --i){
for(int j = n - 2; j > i; --j){
if( _s[i] != _s[j] ){
lcp[ i ][ j ] = 0;
}else{
lcp[ i ][ j ] = lcp[i + 1][j + 1] + 1;
}
}
}
}
只有: lcp[i][j], 且i < j
是有效的!!!
给定一个由[0 - 9]组成的字符串s,长度n是3500。
有n^2次查询[l1, r1, l2, r2],问s[l1, ..., r1]所组成的数字
和 s[l2, ..., r2]所组成的数组
谁大。 (显然,每个查询 必须是O(1) 求出来 )
令: len1 = r1 - l1 + 1, len2 = r2 - l2 + 1.
首先,因为这两个子段 可能有前导零
(如果没有前导零,那么: 如果len1 != len2,就可以直接的判断出大小关系)
(这里也有个性质,对于没有前导零的两个数字,如果两个数字长度不同,那么: 谁长,谁就大)
但是一旦有前导零,这就很难说: s1 = "0000001", s2 = "2"
,虽然s1的长度 非常长,他是小于 s2的。
所以,我们需要先去掉前导零。
可以提前预处理,nex[]数组: nex[i]表示: [i]往后(包括[i]),第一个非0的位置(即,nex[i] >= i)
我们令: L1 = nex[l1], L2 = nex[l2]
假设,L1 <= r1, L2 <= r2。 (否则,可以特判 直接求出)
那么此时问题转换为: 给定两个子串[l1, …, r1] 和 [l2, …, r2](且这两个子串,没有前导0,即:s[l1] != 0, s[l2] != 0)
令: len1 = r1 - l1 + 1, len2 = r2 - l2 + 1.
如果: len1 != len2,这很简单,谁长 谁就大。
当len1 == len2时:
s.substr(l1, len1) 和 s.substr(l2, len1)
,但这是O(n),不是O(1),会超时。但这个暴力算法 思路是正确的,他的思路是: 从左(高位)往 右(低位)扫描,找第一个不同的数位
s1是 l1开始的, s2是 l2开始的。他俩的长度 都是len
FOR(i, 0, len-1, 1){
if( s[l1 + i] != s[l2 + i] ){
return s[l1 + i] <= s[l2 + i];
}
}
我们所找到的,第一个不同的数位[i],他一定是说明: 左侧的[0, .., i-1]
都是相同的!!!
而左侧的这i个元素,我们可以O(1)得到,因为他就是: lcp[l1][l2]的值!!
这正好就是lcp的定义: 最长的 公共 的前缀
比较:s[_l1, ..., _r1] 和 s[_l2, ..., _r2] 对应的整数的大小(保证:s[_l1] != 0, s[_l2] != 0)
bool cmp(int _l1, int _r1, int _l2, int _r2, string & _s){
int len1 = _r1 - _l1 + 1, len2 = _r2 - _l2 + 1;
if( len1 != len2 ){ return len1 < len2; }
if( lcp[ _l1 ][ _l2 ] >= len1 ){
return true;
}
int __lcp = lcp[ _l1 ][ _l2 ];
return _s[ _l1 + __lcp ] < _s[ _l2 + __lcp ];
}
注意,存在:lcp[_l1][_l2] >= len1的情况!!!
比如: s = [1, 1, 1, 1] s1=[1](l1=r1=0),s2=[1](l2=r2=1)
而,lcp[0][1] = 3 > len = 1
。
当:lcp[l1][l2] >= len
时,说明: s[l1,...,r1] == s[l2,...r2]