子串

#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>

using namespace std;

int main() {
int N;
cin >> N; // 读取用户数量N
vector<string> passwords(N); // 存储所有用户的密码
unordered_map<string, int> freq; // 哈希表，记录每个密码出现的频率

// 读取所有密码并统计频率
for (int i = 0; i < N; i++) {
    cin >> passwords[i];
    freq[passwords[i]]++;  // 更新当前密码的频率
}

long long total = 0;  // 初始化总登录次数为0

// 遍历频率表中的每个密码及其出现次数
for (auto &p : freq) {
    const string &s = p.first;  // 当前密码字符串
    set<string> unique_subs;  // 用于存储当前密码的所有唯一子串

    // 生成当前密码的所有子串
    int n = s.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            unique_subs.insert(s.substr(i, j - i + 1));  // 将子串加入集合
        }
    }

    long long count = 0;  // 统计当前密码可以登录的其他用户数

    // 检查每个子串是否在频率表中存在
    for (const string &sub : unique_subs) {
        auto it = freq.find(sub);  // 查找子串在频率表中的位置
        if (it != freq.end()) {
            count += it->second;  // 如果存在，累加其频率
        }
    }

    // 当前密码可以登录的其他用户数为count - 1（减去自身）
    // 乘以当前密码的出现次数，并累加到总次数中
    total += p.second * (count - 1);
}

cout << total << endl;  // 输出总登录次数
return 0;

}