当前位置: 首页 > 工具软件 > LCP > 使用案例 >

lcp最长公共前缀、 比较一个字符串中 任意两个子段的大小。

姜智渊
2023-12-01

LCP

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解决。

  • s[i] != s[j],自然 lcp[i][j] = 0. 开头元素都不同,后面就不用比较了。
  • s[i] == s[j],lcp[i][j] = 1 + lcp[i + 1][j + 1].

从上面样例可以看出,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]

 类似资料: