P3667 Bovine Genomics G 题解

· · 题解

前置知识：字符串Hash (板子：P3370)

一句话题意：给定 n 个A串和 n 个B串，长度均为 m，求一个最短的区间 [l,r]，使得不存在一个A串a和一个B串b，使得 a[l,r]=b[l,r]

在这篇题解中，我们使用a来代表A串中的一个串，b来代表B串中的一个串

使用 a[l, r] 来代表 a串中从 l ~ r 位置的子串

最暴力的想法无非于先从小到大枚举最短的子串长度len，之后再枚举长度为len的所有区间[l, r] (r = l + len - 1, 1 \le l \le r \le m)，暴力判断每个A串 a[l, r] 与每个B串 b[l, r] 有没有重复，时间复杂度O(n ^ 2 * m ^ 3)，显然会超时

我们考虑判断区间[l, r]是否合法的操作进行优化。

具体操作（设当前判断的区间为 [l, r]）：

1.在操作进行前预处理出每个A串中 a[1, x] (1 \le x \le m) 的Hash值，假定Hash时的进制数为 p ，模数为 mod ，那就有Hash[l, r] = (Hash[r] - Hash[l - 1] * p ^ {r - l + 1} + mod) \% mod

预处理代码：

//strA[i][j]: 第i个A串中第j个字符
//hA[i][j]: 第i个A串中前j个字符构成子串的Hash值

for (int i = 1; i <= n; ++i)
{
    for (int j = 1; j <= m; ++j)
    {
        hA[i][j] = hA[i][j - 1] * p + strA[i][j];
    }
}

2.建立一个从整数映射到bool的map，名叫vis，遍历每个A串，将 vis[Hash(a[l, r])] 设为 true

3.遍历每个B串，若 vis[Hash(b[l, r])] 为 true，则当前区间不合法。若对于所有B串都有 vis[Hash(b(l, r))] = false，则当前区间合法。

代码：

//pp[i]为已经预处理好的 p 的 i 次方
map<ull, bool> vis;

bool check(int l, int r)
{
    bool f = 1;
    vis.clear();
    for (int i = 1; i <= n; ++i)
    {
        vis[hA[i][r] - pp[r - l + 1] * hA[i][l - 1]] = 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (vis.count(hB[i][r] - pp[r - l + 1] * hB[i][l - 1]))
        {
            f = 0;
            break;
        }
    }
    if (f)
    {
        return true;
    }
    return false;
}

这样我们就可以把判断区间是否合法的操作从 O(n ^ 2 * m) 优化到 O(n logn * m)，总时间复杂度 O(nlogn * m ^ 3)，仍然会超时。

于是我们考虑二分答案，对从小到大枚举区间长度 len 的操作改为二分枚举，那么总时间复杂度降为 O(nlogn * m^2logm)，可以愉快的AC啦~

以下为AC代码：

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
using namespace std;

int read() //快读
{
    int x = 0;
    char c;
    bool f = 0;
    while (!isdigit(c = getchar()))
    {
        if (c == '-')
        {
            f = 1;
        }
    }
    do
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
    } while (isdigit(c = getchar()));
    if (f)
    {
        return -x;
    }
    return x;
}

typedef unsigned long long ull;

const int maxn = 5e2 + 10;
const ull p = 131;

int n, m;

ull pp[maxn]; //p的i次方
ull hA[maxn][maxn], hB[maxn][maxn]; //Hash前缀和
char strA[maxn][maxn], strB[maxn][maxn]; //串

map<ull, bool> vis;

bool check(int len) //判断区间长度为len时合不合法
{
    for (int l = 1, r = l + len - 1; r <= m; ++l, ++r)
    {
        bool f = 1;
        vis.clear();
        for (int i = 1; i <= n; ++i) //枚举所有A串
        {
            vis[hA[i][r] - pp[r - l + 1] * hA[i][l - 1]] = 1;
        }
        for (int i = 1; i <= n; ++i) //枚举所有B串
        {
            if (vis.count(hB[i][r] - pp[r - l + 1] * hB[i][l - 1])) //这种操作尽量用count函数写，直接用下标方式写的话常数大很多
            {
                f = 0;
                break;
            }
        }
        if (f)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    n = read(), m = read();
    pp[0] = 1; //注意
    for (int i = 1; i <= 500; ++i) //预处理p的i次方
    {
        pp[i] = pp[i - 1] * p;
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", strA[i] + 1);
        for (int j = 1; j <= m; ++j)
        {
            //预处理前缀Hash
            hA[i][j] = hA[i][j - 1] * p + strA[i][j];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", strB[i] + 1);
        for (int j = 1; j <= m; ++j)
        {
            hB[i][j] = hB[i][j - 1] * p + strB[i][j];
        }
    }
    int l = 1, r = m;
    int ans = 0;
    while (l <= r) //二分枚举区间长度
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
}