pku 2001 Shortest Prefixes 排序

ゝ一世哀愁。 2022-07-13 13:16 150阅读 0赞

这题我的做法是排序后, 对前一字符串和后一字符串推断出该字符串的最短前缀.

做完看discuss中, 有人说可以用字典树, 我还没用过, 有时间时打算看一下.

\#include <iostream> \#include <algorithm> \#include <map> \#include <string> using namespace std; \#define MAX(a,b) ((a>b)?(a):(b)) struct Node \{ char str\[21\]; int index; bool operator<(const Node& rhs) \{ return (strcmp(str, rhs.str)<0); \} \}; Node arr\[1000\]; char ret1\[1000\]\[21\]; char ret2\[1000\]\[21\]; int compare(const char\* p1, const char\* p2) \{ int index = 0; while(\*p1++ == \*p2++ && p1 != '/0' && p2 != '/0') index++; return index; \} int main() \{ int n = 0; while(gets(arr\[n\].str)) \{ arr\[n\].index = n; n++; \} if(n == 1) \{ printf("%s %s", arr\[0\].str, arr\[0\].str); return 0; \} sort(arr, arr+n); int index = compare(arr\[0\].str, arr\[1\].str); strcpy(ret1\[arr\[0\].index\], arr\[0\].str); strncpy(ret2\[arr\[0\].index\], arr\[0\].str, index+1); for(int i = 1; i < n-1; ++i) \{ int index1 = compare(arr\[i-1\].str, arr\[i\].str); int index2 = compare(arr\[i\].str, arr\[i+1\].str); strcpy(ret1\[arr\[i\].index\], arr\[i\].str); strncpy(ret2\[arr\[i\].index\], arr\[i\].str, MAX(index1, index2)+1); \} index = compare(arr\[n-2\].str, arr\[n-1\].str); strcpy(ret1\[arr\[n-1\].index\], arr\[n-1\].str); strncpy(ret2\[arr\[n-1\].index\], arr\[n-1\].str, index+1); for(int i = 0; i < n; ++i) printf("%s %s/n", ret1\[i\], ret2\[i\]); return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关 pku 1634 Who's the boss? stl排序+二分查找

\include <iostream> \include <algorithm> \include <vector> using namespace std; struct P

╰半夏微凉°/ 2022年08月09日 14:53/ 0 赞/ 11 阅读

相关 pku 1270 Following Orders DFS+拓扑排序

题意很清晰. 可以利用dfs遍历每一组值,然后加上剪枝条件. 由于剪枝可以利用当前节点和已遍历节点的顺序关系,可以使用拓扑排序. 注意: 输入的第一行不一定是有序的,我在

电玩女神/ 2022年08月09日 14:52/ 0 赞/ 29 阅读

相关 pku 1094 Sorting It All Out 拓扑排序

\include <iostream> \include <stack> using namespace std; int edge\[27\]\[27\]; //图的邻接矩阵

左手的ㄟ右手/ 2022年08月09日 13:52/ 0 赞/ 165 阅读

相关 POJ 2001-Shortest Prefixes【字典树】

Shortest Prefixes <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1

快来打我*/ 2022年07月24日 07:03/ 0 赞/ 151 阅读

相关 pku 2001 Shortest Prefixes 排序

这题我的做法是排序后, 对前一字符串和后一字符串推断出该字符串的最短前缀. 做完看discuss中, 有人说可以用字典树, 我还没用过, 有时间时打算看一下. \inclu

ゝ一世哀愁。/ 2022年07月13日 13:16/ 0 赞/ 151 阅读

相关 pku 3176

\include<stdio.h> int str\[351\]\[351\]; int main() \{ int n,i,j; // freopen("

小鱼儿/ 2022年06月17日 23:29/ 0 赞/ 152 阅读

相关 1651. Shortest Subchain

1651. Shortest Subchain Time limit: 1.0 second Memory limit: 64 MB ![Problem illustr

待我称王封你为后i/ 2022年01月05日 15:41/ 0 赞/ 137 阅读

相关 poj 2001 Shortest Prefixes（字典树）

题目链接：[http://poj.org/problem?][http_poj.org_problem] id=2001 Description A prefi

约定不等于承诺〃/ 2021年10月24日 03:30/ 0 赞/ 259 阅读

相关 Shortest Prefixes 字典树 (前缀树) 入门题题解

Shortest Prefixes 题解（1）题目（2）题解（1）题目 Shortest Prefixes A pr

旧城等待，/ 2021年08月27日 19:47/ 0 赞/ 481 阅读

相关 POJ 2001 Shortest Prefixes【字典树】题解

目录 1.题目 2.代码 1.题目 A prefix of a string is a substring

「爱情、让人受尽委屈。」/ 2021年07月24日 19:34/ 0 赞/ 308 阅读