bzoj2537: [neerc2007]Language Recognition

时间:2021-03-01 12:01:43

Description

DFA(确定性有限状态自动机)是一个有向图,顶点称为状态,边称为转移。每个转移用一个字母标记。对于每个状态s和每个转移l,至多有一个转移从s出发且标记为l。DFA有一个初始状态和若干个结束状态。DFA定义的语言的单词可以由从开始状态到结束状态的路径上所有的字母连接起来。
图中表示一个语言(包括单词:fix,foo,ox)的DFA。第一个DFA有7个状态,它不是最优的。第二个DFA定义的是同一个语言,但只有5个状态。
给定一个语言,包含有限个单词,求出定义该语言的DFA得最少状态数。

Input

    第一行有一个整数n(1<=n<=5000),表示语言的单词数。接下来n行,每行一个单词。每个单词由1到30个小写字母组成。输入的所有单词互不相同。

Output

    一个数,定义该语言的DFA得最少状态数。
等价的状态可以合并,两个状态等价当且仅当同时(不)为结束状态且出边及对应的状态相同
一开始建棵trie然后从叶节点开始将等价状态缩点
#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的更多相关文章

  1. 如何将 Cortana 与 Windows Phone 8&period;1 应用集成 &lpar; Voice command - Natural language recognition &rpar;

    随着 Windows Phone 8.1 GDR1 + Cortana 中文版的发布,相信有很多用户或开发者都在调戏 Windows Phone 的语音私人助理 Cortana 吧,在世界杯的时候我亲 ...

  2. 论文笔记《Tracking Using Dynamic Programming for Appearance-Based Sign Language Recognition》

    一.概述 这是我在做手势识别的时候,在解决手势画面提取的时候看的一篇paper,这里关键是使用了动态规划来作为跟踪算法,效果是可以比拟cameshift和kf的,但在occlusion,gaps或者离 ...

  3. bzoj AC倒序

    Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...

  4. hive

    Hive Documentation https://cwiki.apache.org/confluence/display/Hive/Home 2016-12-22  14:52:41 ANTLR  ...

  5. java开发常用jar包介绍(转载)

    jta.jar 标准JTA API必要 commons-collections.jar 集合类 必要 antlr.jar  ANother Tool for Language Recognition ...

  6. SSH框架整合配置所需JAR包&lpar;SSH整合&rpar;

    转载于:http://www.cnblogs.com/kaige123/p/5719662.html Hibernate Jar: 1.hibernate3.jar,这个是hibernate3.0的核 ...

  7. J2EE相关总结

    Java Commons The Java™ Tutorials: http://docs.oracle.com/javase/tutorial/index.html Java Platform, E ...

  8. POJ题目分类(按初级\中级\高级等分类,有助于大家根据个人情况学习)

    本文来自:http://www.cppblog.com/snowshine09/archive/2011/08/02/152272.spx 多版本的POJ分类 流传最广的一种分类: 初期: 一.基本算 ...

  9. Spring入门学习(一)

    SpringMVC基础平台补充(2016.03.03) 如果想要开发SpringMVC,那么前期依次安装好:JDK(jdk-8u74-windows-x64,安装后配置环境变量JAVA_HOME和CL ...

随机推荐

  1. iOS&colon;选择器控件UIPickerView的详解和演示

    选择器控件UIPickerView: 功能:它能够创建一个类似于密码锁式的单列或多列的选择菜单,用户可以通过它设置的代理来选择需要菜单中的任意的数据.例如创建日历.字体表(类型.大小.颜色).图库等. ...

  2. selenium如何操作cookies实现免登录

    执行接口测试或者某些自动化测试时,为了避免每次访问接口都需要登录操作,可以用访问接口时,把cookies信息传过去. 思路是先登录一次页面,获取到cookies信息,把cookies信息保存到本地文件 ...

  3. 使用jquery获取网页中图片的高度——解惑

    jQuery获取网页中图片的高度 使用jquery获取网页中图片的高度其实很简单,有两种常用的方法都可以打到我们的目的 $("img").whith();(返回纯数字) $(&qu ...

  4. ios2048小游戏

    最近突然想写一个2048的小游戏,由于全部是自定义控件,所以程序看起来冗杂,但是核心的算法部分还是很不错的,大家感兴趣的可以仔细看看. 声明部分: #import <UIKit/UIKit.h& ...

  5. 【算法】后缀自动机&lpar;SAM&rpar; 例题

    算法介绍见:http://www.cnblogs.com/Sakits/p/8232402.html 广义SAM资料:https://www.cnblogs.com/phile/p/4511571.h ...

  6. PowerDsigner 16逆向工程导入mysql

    由于日常数据建模经常使用PowerDesigner,使用逆向工程能更加快速的生成模型提高效率,所以总结使用如下: 1.      安装MYSQL的ODBC驱动 Connector/ODBC 5.1.1 ...

  7. JavaScript 自定义文本框光标——初级版

    文本框(input或textarea)的光标无法修改样式(除了通过color修改光标颜色).但笔者希望个人创建自己的网站时,文本框的光标有属于自己的风格.所以,尝试模拟文本框的光标,设计有自己风格的光 ...

  8. 如何统计TFS代码库中的团队项目所占用的磁盘空间

    在一个开发团队较多的研发中心,当开发人员的代码数据积累到一定程度,TFS系统的磁盘空间的使用率会逐渐成为系统管理员关注的问题.你可能会关注代码库中每个团队项目,甚至每个目录占用的的磁盘空间.不幸的,即 ...

  9. mongoDB系列之(一):10分钟玩转mongoDB

    1. mongoDB是什麽 mongodb是时下流行的NoSql数据库,它的存储方式是文档式存储,并不是Key-Value形式. 存储在集合中的文档,被存储为键-值对的形式.键用于唯一标识一个文档,为 ...

  10. zedboard学习第一篇

    1. 刚开始学习使用,不知道从哪里开始,手上的资料也很乱,至于这个板子需要学什么也不清楚. 2. 第一个工程就从helloworld开始吧,Zed板上的Zynq是一个PS(processing sys ...