P1098 前缀字符串 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2021年6月15日 21:19

c

P1098

回复 0 | 赞 4 | 浏览 6.5k

#include <stdio.h> #include <stdlib.h> typedef struct Node{ struct Node *child[26]; int num; char data; }Node,*Link; void insert(Link T,char datas[20]){ int flag=0; Link p=T; &...

2021年2月2日 13:14

边建Trie树边删多余前缀

P1098

回复 0 | 赞 4 | 浏览 9.4k

两种情况 case1 当前字符串是前面某一个更长串的前缀：判断一下它的son[p][0~25]是否有不为0的元素 case2 当前字符串的前缀是前面某一个短的字符串：建立当前字符串结点路径上如果某一个结点cnt!=0说明这里有前缀 cnt=0删除即可 #include<iostream> #include<string.h> using namespace std; ...

2021年1月30日 23:13

用map的做法

P1098

回复 0 | 赞 7 | 浏览 9.2k

细节比较烦，调了好久关键是要留长的，不能留短的 #include <bits/stdc++.h> using namespace std; int main() { map<string ,int > m; int n; while(cin>>n) { if(n==0)break; string s0; cin>>s0; m[s0]=1; n--; while(n--) { string s; cin>&g...

2020年5月13日 13:09

巧妙的题解

P1098

回复 0 | 赞 10 | 浏览 10.5k

依次遍历每个输入的字符串和目前已经形成的组别，如果与现有的一个组的所有字符串不互为前缀，那么将他加入该组，如果与某个组中的字符串冲突，那么如果该组中的前缀字符串短，则将其替换成较长的，如果他与所有组都冲突，那么另开一个组存它。为什么选最长的？比如如果一个组中现在是 acm yuou 现在输入一个 yuoufsdaf 显然yuou和yuoufsdaf是冲突的，如果我们保留yuou，那么遇到yuout这两个也是冲突的，但是如果我们将yuou换成yuoufsdaf，显然yuout也可以加入该组，贪心的选择长度较长的字符串替换短的，可以使得...

1
2

题目前缀字符串

题解数量14

发布题解在线答疑

热门题解

1 前缀字符串题解：构建前缀树做法C++

2 C++简单模拟

3 巧妙的题解

4 前缀字符串题解：暴力枚举

5 用map的做法

6 前缀字符串 :用前缀树做的,WA,不知道为什么

7 P1098 前缀字符串答疑提问：

8 c

9 边建Trie树边删多余前缀

10 前缀字符串有大佬可以帮忙看一下错在哪里吗？