【模板】字典树 1

19

baoshuo LV 10 MOD @ 2021-10-2 15:12:45

标准的数组 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

13

haze LV 8 @ 2021-8-26 15:24:32

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

将每个字符串看成 $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;
}

7

wmt319 LV 6 @ 2022-3-3 10:47:28

在添加字符串结尾的时候判断一下，之前是否已经是结尾，如果不是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;
}

4

Jerrywang LV 10 @ 2022-10-13 20:59:55

优化单哈希就可以过！

// 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;
}

3

xiaoququ LV 7 @ 2022-11-11 19:23:25

显然，这题也能通过高效的 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;
}

1

Laiyiwen_01 LV 6 @ 2024-7-26 14:38:18

umap 秒了：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, ans = 0;
unordered_map<string, bool> Map;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string s; cin >> s;
        if(!Map[s]) Map[s] = true, ans++;
        else continue;
    }
    cout << ans << endl;
    return 0;
}

1

eason_vijos LV 6 @ 2023-12-25 20:33:23

这个问题可以通过使用集合（Set）来解决。集合是一种不包含重复元素的数据结构，因此将所有的字符串放入集合中，最后统计集合的大小即可得到不同的字符串数量（50分）

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

int main() { int n; cin >> n;

 set<string> uniqueStrings;

 for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      uniqueStrings.insert(s);
 }

 cout << uniqueStrings.size() << endl;

 return 0;

}

1

陆冠丞 LV 6 @ 2023-8-8 11:00:37

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;
}

1

Leo2 LV 10 @ 2023-3-23 20:07:35

#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;
}
~~？？？~~

0

tyzxzxf LV 5 @ 2024-6-23 9:59:15

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

int n, cnt = 1, t[10000005][26], info[10000005], ans;
string s;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u = 1;
        cin >> s;
        for (auto c : s) {
            if (t[u][c - 'a'] == 0) t[u][c - 'a'] = ++cnt;
            u = t[u][c - 'a'];
        }
        if (!info[u]) ans++, info[u] = 1;
    }
    cout << ans;
    return 0;
}

0

doc LV 7 @ 2023-10-27 22:54:35

#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;
}

0

linxioj LV 1 @ 2023-4-13 10:50:24

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());
}

-9

周文轩 LV 5 @ 2022-5-13 9:13:03

#include 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; }

-41

ty1018 LV 5 @ 2021-8-24 14:37:20

#include <bits/stdc++.h> using namespace std; unordered_set 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

14 条题解

信息

状态

开发

支持

14 条题解

【模板】字典树 1

信息

状态

开发

支持

还没有账户？

登录