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

时间：2024-10-08 16:28:40

catalog

  • LCP
    • 应用— 字符串中任意两个子段的大小

LCP

lcp： longest common prefix

lcp[i][j]为： s[i, i+1, …, n] 和 s[j, j+1, …, n] 这两个串，的最长公共前缀 的长度。
即(i, lcp[i][j]) = (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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

当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;
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

只有： 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时:

  • 暴力算法是： 比较(l1, len1) 和 (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]; 
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

我们所找到的，第一个不同的数位[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 ]; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

注意，存在：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]

相关文章