Description
Input
Output
#include<cstdio>
#include<algorithm>
typedef unsigned long long u64;
const int N=;
int n,ans=;
int nx[N][],id[N],pv[N],e[N],p=;
char s[];
bool ed[N];
int q[N],qp=,q1[N];
u64 h[N];
bool cmp(int a,int b){return h[a]<h[b];}
u64 hash(int w){
u64 v=;
for(int i=;i<;i++)v=v*+id[nx[w][i]];
if(e[w])v+=;
return v;
}
int main(){
scanf("%d",&n);
while(n--){
scanf("%s",s);
int w=;
for(int i=;s[i];i++){
int c=s[i]-'a';
if(!nx[w][c])nx[w][c]=++p;
pv[nx[w][c]]=w;
w=nx[w][c];
}
e[w]=;
}
for(int i=;i<=p;i++)id[i]=i;
for(int i=;i<=p;i++)if(e[i]){
bool is=;
for(int j=;j<;j++)if(nx[i][j]){is=;break;}
if(is)ed[q[qp++]=i]=;
}
while(qp){
int m=qp;
qp=;
for(int i=;i<m;i++)h[q1[i]=q[i]]=hash(q[i]);
std::sort(q1,q1+m,cmp);
for(int i=,j=;i<m;i=j){
while(h[q1[i]]==h[q1[j]])id[q1[j++]]=q1[i];
if(i+<j)for(int k=i;k<j;k++)if(!ed[pv[q1[k]]])ed[q[qp++]=pv[q1[k]]]=;
}
}
for(int i=;i<=p;i++)if(id[i]==i)++ans;
printf("%d",ans);
return ;
}
bzoj2537: [neerc2007]Language Recognition的更多相关文章
-
如何将 Cortana 与 Windows Phone 8.1 应用集成 ( Voice command - Natural language recognition )
随着 Windows Phone 8.1 GDR1 + Cortana 中文版的发布,相信有很多用户或开发者都在调戏 Windows Phone 的语音私人助理 Cortana 吧,在世界杯的时候我亲 ...
-
论文笔记《Tracking Using Dynamic Programming for Appearance-Based Sign Language Recognition》
一.概述 这是我在做手势识别的时候,在解决手势画面提取的时候看的一篇paper,这里关键是使用了动态规划来作为跟踪算法,效果是可以比拟cameshift和kf的,但在occlusion,gaps或者离 ...
-
bzoj AC倒序
Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...
-
hive
Hive Documentation https://cwiki.apache.org/confluence/display/Hive/Home 2016-12-22 14:52:41 ANTLR ...
-
java开发常用jar包介绍(转载)
jta.jar 标准JTA API必要 commons-collections.jar 集合类 必要 antlr.jar ANother Tool for Language Recognition ...
-
SSH框架整合配置所需JAR包(SSH整合)
转载于:http://www.cnblogs.com/kaige123/p/5719662.html Hibernate Jar: 1.hibernate3.jar,这个是hibernate3.0的核 ...
-
J2EE相关总结
Java Commons The Java™ Tutorials: http://docs.oracle.com/javase/tutorial/index.html Java Platform, E ...
-
POJ题目分类(按初级\中级\高级等分类,有助于大家根据个人情况学习)
本文来自:http://www.cppblog.com/snowshine09/archive/2011/08/02/152272.spx 多版本的POJ分类 流传最广的一种分类: 初期: 一.基本算 ...
-
Spring入门学习(一)
SpringMVC基础平台补充(2016.03.03) 如果想要开发SpringMVC,那么前期依次安装好:JDK(jdk-8u74-windows-x64,安装后配置环境变量JAVA_HOME和CL ...
随机推荐
-
iOS:选择器控件UIPickerView的详解和演示
选择器控件UIPickerView: 功能:它能够创建一个类似于密码锁式的单列或多列的选择菜单,用户可以通过它设置的代理来选择需要菜单中的任意的数据.例如创建日历.字体表(类型.大小.颜色).图库等. ...
-
selenium如何操作cookies实现免登录
执行接口测试或者某些自动化测试时,为了避免每次访问接口都需要登录操作,可以用访问接口时,把cookies信息传过去. 思路是先登录一次页面,获取到cookies信息,把cookies信息保存到本地文件 ...
-
使用jquery获取网页中图片的高度——解惑
jQuery获取网页中图片的高度 使用jquery获取网页中图片的高度其实很简单,有两种常用的方法都可以打到我们的目的 $("img").whith();(返回纯数字) $(&qu ...
-
ios2048小游戏
最近突然想写一个2048的小游戏,由于全部是自定义控件,所以程序看起来冗杂,但是核心的算法部分还是很不错的,大家感兴趣的可以仔细看看. 声明部分: #import <UIKit/UIKit.h& ...
-
【算法】后缀自动机(SAM) 例题
算法介绍见:http://www.cnblogs.com/Sakits/p/8232402.html 广义SAM资料:https://www.cnblogs.com/phile/p/4511571.h ...
-
PowerDsigner 16逆向工程导入mysql
由于日常数据建模经常使用PowerDesigner,使用逆向工程能更加快速的生成模型提高效率,所以总结使用如下: 1. 安装MYSQL的ODBC驱动 Connector/ODBC 5.1.1 ...
-
JavaScript 自定义文本框光标——初级版
文本框(input或textarea)的光标无法修改样式(除了通过color修改光标颜色).但笔者希望个人创建自己的网站时,文本框的光标有属于自己的风格.所以,尝试模拟文本框的光标,设计有自己风格的光 ...
-
如何统计TFS代码库中的团队项目所占用的磁盘空间
在一个开发团队较多的研发中心,当开发人员的代码数据积累到一定程度,TFS系统的磁盘空间的使用率会逐渐成为系统管理员关注的问题.你可能会关注代码库中每个团队项目,甚至每个目录占用的的磁盘空间.不幸的,即 ...
-
mongoDB系列之(一):10分钟玩转mongoDB
1. mongoDB是什麽 mongodb是时下流行的NoSql数据库,它的存储方式是文档式存储,并不是Key-Value形式. 存储在集合中的文档,被存储为键-值对的形式.键用于唯一标识一个文档,为 ...
-
zedboard学习第一篇
1. 刚开始学习使用,不知道从哪里开始,手上的资料也很乱,至于这个板子需要学什么也不清楚. 2. 第一个工程就从helloworld开始吧,Zed板上的Zynq是一个PS(processing sys ...