2021牛客寒假第四场武辰延的字符串（二分+哈希）-白红宇

2021牛客寒假第四场武辰延的字符串（二分+哈希）

阅读量：624 次

发布时间：2019-03-12

本文共 2260 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要找到两个字符串 s 和 t，其中 s 的非空前缀连起来能够形成 t 的前缀。具体来说，我们需要统计有多少个 s 的前缀是 t 的前缀。

方法思路

问题分析：

我们需要找到 s 的所有前缀，并检查这些前缀是否是 t 的前缀的一部分。

这可以通过预处理 s 和 t 的前缀哈希值来高效实现，以减少哈希冲突的概率。

哈希预处理：

预处理 s 和 t 的前缀哈希值和幂次数组。哈希值用于快速比较两个字符串的前缀是否相同，幂次数组用于计算哈希值。

比较前缀：

对于每个可能的前缀长度 k，检查 s 的前 k 个字符的哈希值是否等于 t 的前 k 个字符的哈希值。如果相等，则计数加一。

优化：

由于 s 和 t 的长度可能不同，我们只需要检查到两者长度较小的那个。

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
          using namespace std; #define ll long long #define ull unsigned ll #define inf 0x3f3f3f3f #define mod 1e9+7 #define base 131 #define base2 233 ll read() { ll res = 0, flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { res = (res < 10) + (res < 1) + (ch - '0'); ch = getchar(); } return res * flag; } int main() { string s = read_str(), t = read_str(); int len_s = s.size(), len_t = t.size(); int max_len = min(len_s, len_t); // 预处理哈希和幂次数组 vector
          
            p(max_len + 2, 1), p2(max_len + 2, 1); vector
           
             sum1(max_len + 2, 0), sum2(max_len + 2, 0); vector
            
              pre1(max_len + 2, 0), pre2(max_len + 2, 0); for (int i = 1; i <= max_len; ++i) { p[i] = p[i-1] * base % mod; p2[i] = p2[i-1] * base2 % mod; sum1[i] = (sum1[i-1] * base + s[i-1]) % mod; pre1[i] = (pre1[i-1] * base2 + s[i-1]) % mod; sum2[i] = (sum2[i-1] * base + t[i-1]) % mod; pre2[i] = (pre2[i-1] * base2 + t[i-1]) % mod; } auto get_hash = [](int l, int r, vector
             
              & a, vector
              
               & p) { ll hash = (a[r] - a[l-1] * p[r - l + 1]) % mod; if (hash < 0) hash += mod; return hash; }; ll ans = 0; for (int i = 1; i <= max_len; ++i) { if (s[i-1] != t[i-1]) break; int l = 0, r = len_t - i; ll target = get_hash(1, r, sum2, pre2); ll current = 0; int max_r = r; while (r > 0) { int mid = max_r / 2 + 1; if (mid > max_r) break; ll h = get_hash(1, mid, sum1, pre1); if (h == target) { current = mid; l = mid + 1; max_r = mid - 1; } else if (h < target) { max_r = mid - 1; } else { r = mid - 1; } } if (current > 0) ans += current; } cout << ans << endl; return 0; }