POJ2001字典树

2024-09-09 07:08
文章标签 字典 poj2001

本文主要是介绍POJ2001字典树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给出n个单词,求出每个单词的非公共前缀,如果没有,则输出自己。

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;public class Main {public static void main(String[] args)  {new Task().solve();}
}class Task {class Node {int cnt ;Node[] next ;Node(){cnt = 0 ;next = new Node[26] ;}}void add(Node root , String word){Node now = root ;for(char c : word.toCharArray()){int idx = c - 'a' ;if(now.next[idx] == null)now.next[idx] = new Node() ;now = now.next[idx] ;now.cnt++ ;}}String query(Node root , String word){Node now = root ;for(int i = 0 ; i < word.length() ; i++){int idx = word.charAt(i) - 'a' ;now = now.next[idx] ;if(now.cnt == 1) return word.substring(0, i+1) ;}return word ;}void solve() {Node root = new Node() ;List<String> words = new ArrayList<String>() ;while(in.hasNext()){String word = in.next() ;words.add(word) ;add(root, word) ;}for(String word : words) out.println(word + " " + query(root, word)) ;out.flush();}InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);
}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = new StringTokenizer("");}private void eat(String s) {tokenizer = new StringTokenizer(s);}public String nextLine() {try {return reader.readLine();} catch (Exception e) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}


这篇关于POJ2001字典树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150497

相关文章

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序

POJ3617(字典序最小问题)

书中43页 此题有坑点,PE了40分钟.也是醉了....题目要求每80个字符才换行,而且最后一个如果恰好就不用换,这不是无聊嘛....... #include <iostream>#include <cstdio>#include <cstring>using namespace std;int n,m;char S[2100],P[2100];int main(){#ifd

POJ 2001 Shortest Prefixes(字典树入门)

题目: http://poj.org/problem?id=2001 题意: 找到多个字符串中,各自唯一的最短子串,例如 carte 与 carce 各自唯一的最短子串为cart与carc,即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码: #include<stdio.h>#include<string>typedef str

Oracle数据库(数据字典、表空间、表的创建、视图)

知识点引用: http://www.2cto.com/database/201207/142874.html http://blog.csdn.net/haiross/article/details/11772847 一. 彻底卸载Oracle 方式1、重装操作系统 方式2、 2.1 DBCA删除数据库开始 → 程序 → Oracle → 开发与移植工具 → Datab

Python的字符串,list,tuple,set,字典操作详解

1.字符串python是要创建成字符串的元素,其中的每个字母都是单一的子串,把它放在' '单引号或是'' ''引号中,就完成了python 字符串的创建。#str强制转换>>> a=123>>> b=str(a) #将整数转化为字符串>>> b'123'>>> a=[1,2,3]>>> b=str(a) #将list转化为字符串>>> b'[1, 2, 3]'#字符串下

OC中数组、字典、集合常用方法的运用

/* ====================== 一 NSArray========================          1.创建对象          1.1初始化方法(2) //一般程序有问题先检查初始化          1.2类方法          1.3字面量方法          2.数组查找          2.1通过下标访问对象[ .[i]]

python pickle 模块用于保存python内存数据(包括实例对象、字典、列表等所有python中的数据)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言基本用法 前言 Python 的 pickle 模块用于序列化和反序列化 Python 对象。这意味着你可以将 Python 对象(如列表、字典、类实例等)转换为字节流(序列化),并将其保存到文件中或在网络上传输,然后在需要的时候将其恢复为原始 Python 对象(反序列化)。 常见用途

Python 从入门到实战8(字典)

我们的目标是:通过这一套资料学习下来,通过熟练掌握python基础,然后结合经典实例、实践相结合,使我们完全掌握python,并做到独立完成项目开发的能力。       上篇文章我们通过举例学习了python 中元组的定义及相关操作。今天详细讲述字典的定义及相关的操作,也是经常使用到的。 1、字典的定义 字典是由{}括住的,内容以“键-值对”的形式存储的无序序列。 字典的主要特点如下:

Python 字典详解

Python 字典 : 字典是另一种可变容器模型,且可存储任意类型对象。 字典的每个键值(key=>value)对用冒号(:)分割,每个对之间用逗号(,)分割,整个字典包括在花括号({})中 ,格式如下所示: d = {key1 : value1, key2 : value2 } 键必须是唯一的,但值则不必。 值可以取任何数据类型,但键必须是不可变的,如字符串,数字或元组。 一个简单的

Python字典小练习

#coding:utf-8 实现一个简单的数据库 字典使用人名作为键,每个人用另一个字典来表示,其键”phone”和”addr”分别表示他们的联系电话和地址。 people= {"王琳":{"phone":"15192060925","addr":"山东省青岛市市北区天怡景园"},"刘涛":{"phone":"15863015300","addr":"山东省青岛市市北区天怡景园"},"蔡明"