标准的数组 Trie 。

#include <bits/stdc++.h>

using namespace std;

int n, p = 1, trie[10000005][26], size[10000005];
char s[4000005];

void insert(int u, const char* s) {
    if (!strlen(s)) {
        size[u] = 1;
        return;
    }
    if (!trie[u][s[0] - 'a']) trie[u][s[0] - 'a'] = ++p;
    insert(trie[u][s[0] - 'a'], s + 1);
}

void calcsize(int u) {
    for (int i = 0; i < 26; i++) {
        if (trie[u][i]) {
            calcsize(trie[u][i]);
            size[u] += size[trie[u][i]];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        insert(1, s);
    }
    calcsize(1);
    printf("%d\n", size[1]);
    return 0;
}

Personal Homepage | Blog | OI Blog

显然，这题也可以考虑字符串哈希。

将每个字符串看成 $p$ 进制数,将其对 $M$ 取模后的结果作为哈希值。

例如 $S=abb,p=10,M=16384$ , $hs=122$

通常 $P=13331,131$ $M=2^{64}$ 或者较大质数。

我写的是拉 $M$ 个 vector 存另一模数的哈希值。

int main() {
    int n;
    scanf("%d", &n);
    int ans = n;

    for (int i = 1; i <= n; ++i) {
        string str;
        cin >> str;
        int len = str.length();
        //cerr<<104<<endl;
        ll hs1 = 0, hs2 = 0;

        for (int j = 0; j < len; ++j) {
            hs1 *= p, hs2 *= p;
            hs1 += str[j], hs2 += str[j];
            hs1 %= mod1, hs2 %= mod2;
        }

        //cerr<<hs1<<' '<<hs2<<endl;
        int fl = 0;

        for (int j = 0; j < h[hs1].size(); ++j) {
            if (h[hs1][j] == hs2) {
                ans--;
                fl = 1;
                break;
            }
        }

        if (fl == 0)
            h[hs1].push_back(hs2);
    }

    cout << ans << endl;
    return 0;
}

在添加字符串结尾的时候判断一下，之前是否已经是结尾，如果不是ans++，如果是就不执行++操作。最后主函数直接输出ans即可。

#include<iostream>
using namespace std;

typedef long long ll;

const int N = 1e7;

int n,m,ans = 0;
int trie[N][26],tot = 1;
bool End[N];

void insert(string str)
{
    int len = str.length(),p = 1;
    for(int k = 0;k < len; k ++)
    {
        int ch = str[k] - 'a';
        if(trie[p][ch] == 0)
        {
            trie[p][ch] = ++ tot;
        }
        p = trie[p][ch];
    }
    if(!End[p])
    {
        End[p] = true;
        ans ++;
    }
}

string str;

int main()
{
    cin >> n;
    while(n --)
    {
        cin >> str;
        insert(str);
    }
    cout << ans << endl;
}

优化单哈希就可以过！

// code
#pragma GCC optimize("Ofast", "inline")
#include <bits/stdc++.h>
#define int unsigned long long
#define SIZE 200010
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

char s[4000005];
unordered_map<int, int> S;

signed main()
{
	signed n; scanf("%d", &n);
	for(signed i=0; i<n; i++)
	{
		scanf("%s", s);
		int x=0;
		for(signed i=0; i<strlen(s); i++) x=(x*(1<<7)+s[i]);
		S[x];
	}
	printf("%u", S.size());

    return 0;
}

显然，这题也能通过高效的 unordered_set 水过，其单次操作的时间复杂度均摊是 $O(1)$ 的。

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int MAXN = 1e6 + 5;
unordered_set<string> s;
string t;
int cnt = 0, n;

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t;
        if (s.find(t) == s.end()) {
            ++cnt;
            s.insert(t);
        }
    }
    cout << cnt << endl;
    return 0;
}

STL轻松水过

#include<bits/stdc++.h>
using namespace std;
int n; 
unordered_map<string,bool> mp;
int cnt=0;
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	while(n--)
	{
		cin>>s;
		if(mp[s]==0)
			cnt++;
		mp[s]=1;
	}
	cout<<cnt;
	return 0;
}

#include<iostream>
using namespace std;

typedef long long ll;

const int N = 1e7;

int n,m,ans = 0;
int trie[N][26],tot = 1;
bool End[N];

void insert(string str)
{
    int len = str.length(),p = 1;
    for(int k = 0;k < len; k ++)
    {
        int ch = str[k] - 'a';
        if(trie[p][ch] == 0)
        {
            trie[p][ch] = ++ tot;
        }
        p = trie[p][ch];
    }
    if(!End[p])
    {
        End[p] = true;
        ans ++;
    }
}

string str;

int main()
{
    cin >> n;
    while(n --)
    {
        cin >> str;
        insert(str);
    }
    cout << ans << endl;
}
~~？？？~~

use std::io::stdin;
use std::str::FromStr;
use std::collections::HashSet;

fn read<T: FromStr>() -> Result<T, T::Err> {
    let mut tmp = String::new();
    stdin().read_line(&mut tmp).unwrap();
    tmp.trim().parse::<T>()
}

fn main() {
    let mut len_lines = read::<i32>().unwrap();
    let mut set = HashSet::new();
    let sin = stdin();
    while len_lines > 0 {
        let mut s = String::new();
        sin.read_line(&mut s).unwrap();
        set.insert(s);
        len_lines -= 1;
    }
    println!("{}", set.len());
}

#include<iostream> using namespace std; string s; string s2; int main(){ int n,i,j,count; cin>>n; getline(cin,s); int l=s.length(); for(i=0;i<n-1;i++){ for(j=0;j<l;j++){ getline(cin,s2); if(s[j]==s2[j]) continue; else{ count++; break; } } } return 0; }

#include <bits/stdc++.h> using namespace std; unordered_set<string> s; string a; int n; int main() { cin.tie(0), cout.tie(0), ios::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a, s.insert(a); cout << s.size(); return 0; } //记得开O2