用c++判断大量字符串是否相等，给出时间复杂度较低的代码

可以用哈希表来实现。先给每个字符串分配一个唯一的哈希值，如果两个字符串的哈希值相同，则判断它们是否真的相等。具体实现如下：

#include <stdio.h>
#include <string.h>

#define MAX_N 1000000
#define MOD 1000000007

typedef unsigned long long u64;

u64 hash[MAX_N], p[MAX_N];

// 为每个字符串计算哈希值
void init_hash(char *str[], int n) {
    p[0] = 1;
    for (int i = 0; i < n; ++i) {
        int len = strlen(str[i]);
        hash[i] = 0;
        for (int j = 0; j < len; ++j) {
            hash[i] = hash[i] * 31 + str[i][j];
            hash[i] %= MOD;
        }
    }
    for (int i = 1; i < n; ++i) {
        p[i] = p[i - 1] * 31;
        p[i] %= MOD;
    }
}

// 判断两个字符串是否相等
int is_equal(char *a, char *b, int len) {
    for (int i = 0; i < len; ++i) {
        if (a[i] != b[i])
            return 0;
    }
    return 1;
}

// 判断两个字符串是否相等
int is_equal_hash(int ai, int aj, int bi, int bj) {
    if (aj - ai != bj - bi)
        return 0;
    u64 hash1 = (hash[aj] - hash[ai] * p[aj - ai]) % MOD;
    if (hash1 < 0)
        hash1 += MOD;
    u64 hash2 = (hash[bj] - hash[bi] * p[bj - bi]) % MOD;
    if (hash2 < 0)
        hash2 += MOD;
    if (hash1 != hash2)
        return 0;
    return is_equal(str[ai], str[bi], aj - ai + 1);
}

char *str[MAX_N];

int main() {
    int n = 0;
    while (scanf("%s", str[n]) != EOF) {
        ++n;
    }
    init_hash(str, n);
    // 暴力判断每个字符串是否相等
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (is_equal(str[i], str[j], strlen(str[i]))) {
                printf("%s %s\n", str[i], str[j]);
            }
        }
    }
    return 0;
}

这种方法的时间复杂度为 $O(n^2 L)$，其中 $n$ 是字符串的个数，$L$ 是最长字符串的长度。实际上它的表现并不好，只适用于字符串较短的情况。如果字符串比较长（比如 $10^5$），那么时间复杂度会变得非常高。要进一步优化的话，可以考虑构建类似于哈希表的数据结构来加速查找。