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

为了解决这个问题，我们需要判断给定的DNA序列中两个区间内的子串是否完全相同。为了高效处理大量查询，我们使用前缀哈希技术来快速比较子串。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const long long MOD = 1e18 + 3;
int main() {
    // 读取所有输入到一个数组中
    char buffer[2000000]; // 假设最大输入量
    int total = 0;
    while (true) {
        int nread = cin.read(buffer, sizeof(buffer), -1);
        if (nread == -1) break;
        total += nread;
    }
    char* ptr = buffer;
    int pos = 0;
    // 读取DNA字符串S
    int n = 0;
    while (ptr[pos] != '\n' && pos < total) {
        pos++;
        n++;
    }
    string S(ptr, ptr + n);
    pos++;
    // 读取查询次数m
    int m = 0;
    while (ptr[pos] != '\n' && pos < total) {
        pos++;
        m++;
    }
    pos++;
    // 读取所有查询
    vector
      
       
        > queries;
    for (int i = 0; i < m; ++i) {
        while (ptr[pos] == '\n') {
            pos++;
        }
        int l1 = ptr[pos++] - '0';
        int r1 = ptr[pos++] - '0';
        int l2 = ptr[pos++] - '0';
        int r2 = ptr[pos++] - '0';
        queries.push_back(make_tuple(l1, r1, l2, r2));
    }
    // 预处理基数的幂次数组p和前缀哈希数组f
    vector
        
          p(n + 1), f(n + 1); p[0] = 1; for (int i = 1; i <= n; ++i) { p[i] = (p[i - 1] * 131) % MOD; } f[0] = 0; for (int i = 1; i <= n; ++i) { long long c = S[i - 1] - 'a' + 1; f[i] = (f[i - 1] * 131 + c) % MOD; } // 处理每个查询 for (const auto& query : queries) { int l1, r1, l2, r2; tie(l1, r1, l2, r2) = query; int len1 = r1 - l1 + 1; int len2 = r2 - l2 + 1; // 计算区间哈希值 long long h1 = (f[r1] - (f[l1 - 1] * p[len1]) % MOD) % MOD; h1 = (h1 + MOD) % MOD; // 处理负数情况 long long h2 = (f[r2] - (f[l2 - 1] * p[len2]) % MOD) % MOD; h2 = (h2 + MOD) % MOD; if (h1 == h2) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }
        
       
      
     
    
   

代码解释

这种方法确保了每个查询的时间复杂度为O(1)，总体复杂度为O(n + m)，适用于大规模数据。

转载地址：http://kaim.baihongyu.com/