P1098 前缀字符串 - 题解

登录注册上岸

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

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

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

2024年4月14日 21:19

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

P1098

回复 2 | 赞 0 | 浏览 582

#include<bits/stdc++.h> using namespace std; bool compair(const string& s1, const string& s2){ if (s1.size() > s2.size()) return false; // s1 不能是 s2 的前缀 for (int i = 0; i < s1.size(); i++) { if (s1[i] != s2[i...

2023年7月29日 13:13

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

P1098

回复 0 | 赞 3 | 浏览 1.4k

构建前缀树做法 #include "iostream" #include "cstdio" #include "cstring" using namespace std; struct Node{ int count; Node* child[26]; Node(){ count=0; memset(child, 0,sizeof(child)); } }; //字符串加入前缀树中 void insertTree(string s,Node* root){ if(s.em...

2023年6月29日 19:19

C++简单模拟

P1098

回复 0 | 赞 2 | 浏览 1.1k

题目数据范围很小，可以直接暴力枚举做，时间复杂度O(n^2) #include<iostream> #include<cstring> using namespace std; const int N = 200; string s[N]; string h[N]; bool is_pre(string s1, string s2) { bool flag = true; string a, b; if(s1.size()<s2.size()) a = s1, b = s2; else ...

2021年1月20日 16:40

打卡

P1098

回复 1 | 赞 1 | 浏览 9.7k

教程代码 //1161 //通不过的代码，主要是creat_tree部分，写法不一样 #include<iostream> #include<string> #include<cstring> #include<stack> #include<vector> #include <queue> #include <functional> using namespace std; const int maxn=26; typedef struct TrieNode{ int...

2021年6月15日 21:19

c

P1098

回复 0 | 赞 1 | 浏览 6.0k

#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 | 赞 0 | 浏览 8.9k

两种情况 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 | 赞 1 | 浏览 8.7k

细节比较烦，调了好久关键是要留长的，不能留短的 #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 | 赞 4 | 浏览 9.7k

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

题目前缀字符串

题解数量8

热门题解

1 巧妙的题解

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

3 C++简单模拟

4 打卡

5 c

6 用map的做法

7 边建Trie树边删多余前缀

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