【算法入门教育赛1E】最长公共前缀 - 字符串哈希 | 二分 | C++题解与代码

题目链接：https://www.starrycoding.com/problem/163

题目描述

牢$e$在$StarryCoding$的入门教育赛报名单上遇到了许多名字$s_1,s_2,...,s_n$，他想知道由这些人的名字所构成的集合中，最长公共前缀的长度是多少？

输入格式

第一行一个整数$T(1\le T\le 1000)$表示样例个数。

对于每一个样例：

第一行一个整数$n(1\le n\le 10^4)$表示名单长度。

接下来$n$行，每行一个字符串表示参赛选手的名字$s_i(1\le |s_i|\le 10^3)$，名字仅包含大小写字母和数字，没有空格、换行等符号。

数据保证$1\le \sum n\le 10^5$

输出格式

对于每组样例，输出一个整数，表示最长公共前缀的长度。

输入样例1

2
5
starry114514
starry2333
starrycoding
starrabcd
starryhhh
3
sYRuOqnMKs
bgPMcT
MRhMZuxe

输出样例1

5
0

题解

二分 + 字符串进制哈希。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef unsigned long long ull;

const int N = 1e4 + 9;
char s[N][1003];
int n;
const ull base = 131;
ull h[N][1003];

void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        int m = strlen(s[i] + 1);
        for (int j = 1; j <= m; ++j)
        {
            h[i][j] = h[i][j - 1] * base + (ull)s[i][j];
        }
    }
}

bool check(int mid)
{
    for (int i = 1; i <= n; ++i)
    {
        if ((i > 1 && h[i][mid] != h[i - 1][mid]) || strlen(s[i] + 1) < mid)
            return false;
    }
    return true;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> s[i] + 1;
    init(n);
    int l = 0, r = 1001;
    while (l + 1 != r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _;
    cin >> _;
    while (_--)
        solve();
    return 0;
}