BZOJ 1212 HNOI2004 L语言 AC自己主动机(Trie树)+动态规划

BZOJ 1212 HNOI2004 L语言 AC自己主动机(Trie树)+动态规划

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

标题效果:给定词的列表,并m串 每个字符串q个最长前缀,这个前缀可满足拆分成一些字符串 这些字符串中存在的词汇太

再也不怕错误的数据范围……有一个很明显Trie树能解决的问题竟然被我写的AC自己主动机……

单词列表插入所有字AC主动机 每一个单词所在的节点记录这个单词的长度

然后对于每一个字符串 用f[i]表示长度为i的前缀能否拆分成单词表中的单词 跑AC自己主动机

对于每一个匹配的节点 从这个节点開始到根的fail路径上的全部len f[i]|=f[i-len]

找到最大的为1的f[i]即是答案

因为单词长度最大为10 所以直接用Trie树暴力就可以

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1050000
using namespace std;
struct Trie{
	int len;
	Trie *fail,*son[26];
	void* operator new (size_t size);
}*root,*mempool,*C;
int n,m;
char s[M];
void* Trie :: operator new (size_t size)
{
	if(C==mempool)
	{
		C=new Trie[1<<15];
		mempool=C+(1<<15);
		memset(C,0,sizeof(Trie)*(1<<15) );
	}
	return C++;
}
void Insert(Trie*&p,char *pos,int dpt)
{
	if(!p) p=new Trie;
	if(!*pos)
	{
		p->len=dpt;
		return ;
	}
	Insert(p->son[(*pos)-'a'],pos+1,dpt+1);
}
void BFS()
{
	static Trie* q[1<<16];
	static unsigned short r,h;
	int i;Trie *temp;
	for(i=0;i<26;i++)
		if(temp=root->son[i])
		{
			temp->fail=root;
			q[++r]=temp;
		}
	while(r!=h)
	{
		Trie *p=q[++h];
		for(i=0;i<26;i++)
			if(p->son[i])
			{
				temp=p->fail;
				while( temp!=root && !temp->son[i] )
					temp=temp->fail;
				if( temp->son[i] )
					temp=temp->son[i];
				p->son[i]->fail=temp;
				q[++r]=p->son[i];
			}
	}
}
int Aho_Corasick_Automaton()
{
	int i,re=0;
	Trie *p=root,*temp;
	static bool f[M];f[0]=1;
	for(i=1;s[i];i++)
	{
		f[i]=0;
		while( p!=root && !p->son[s[i]-'a'] )
			p=p->fail;
		if(p->son[s[i]-'a'])
		{
			p=p->son[s[i]-'a'];
			for(temp=p;temp!=root;temp=temp->fail)
				if(temp->len)
				{
					f[i]|=f[i-temp->len];
					if(f[i]) break;
				}
		}
		if(f[i]) re=i;
	}
	return re;
}
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%s",s+1),Insert(root,s+1,0);
	BFS();
	for(i=1;i<=m;i++)
	{
		scanf("%s",s+1);
		cout<<Aho_Corasick_Automaton()<<endl;
	}
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117266.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 快速搭建静态网站生成器「建议收藏」

    快速搭建静态网站生成器「建议收藏」快速搭建静态网站生成器下面有许多静态页面生成器,大家可以根据需求学以致用。快速搭建静态网站:https://www.staticgen.com/

  • 接口测试框架之Karate

    接口测试框架之Karate之前在一些博客中零零散散看到过对Karate介绍,基本都和Graphql接口测试绑定在一起,似乎测试GraphqlAPI首选的工具之一就是Karate。后来一位开发大牛也推荐我使用Karate,他提到自己之前的项目中就用框架测试Graphql接口,且强调该框架在ThoughtWorks的技术雷达中。想着Graphql使用越来越广泛,且技术雷达中介绍过的框架一般都有其独特优势,带着这些好奇心我花了…

    2022年10月23日
  • java calendar类_Java Calendar类

    java calendar类_Java Calendar类Calendar类概述/***java.util.Calendar类:是一个日历类*Calendar类是一个抽象类,里边提供了很多操作日历字段的方法*如:YEAR、MONTH、DAYOFMONTH、HOUR**Calendar类无法直接创建对象使用,里边有一个静态方法叫getInstance(),*getInstance()方法返回了Calendar类的子…

  • NTP校时设置

    NTP校时设置一、WindowsServer2008–TimeServer前言:国家时间与频率标准实验室 &amp;&amp;NTP服务器 也可以忽略1~6直接跳7 如果已改过机码请使用 1    Cmd:2     netstopw32time3     w32tm/unregister4     w32tm/register…

  • java中json字符串和java对象的转换「建议收藏」

    java中json字符串和java对象的转换「建议收藏」文章目录1、Java与前台的交互2、解析JSON的第三方工具3、JSON数据和Java对象的相互转换Java对象转换JSON字符串JSON字符串转为Java对象1、Java与前台的交互作为后台,Java不仅需要接收前台传递过来的数据,还需要将数据库中的数据查出来打包好发…

  • java maven 配置环境变量_maven 环境变量的配置详解

    java maven 配置环境变量_maven 环境变量的配置详解我的电脑是win10_64位的。一、安装,我使用的是免安装版的,直接解压缩就可以使用。二、配置环境变量。1.打开环境变量配置。右键计算机→属性→高级系统设置→高级→环境变量,在系统变量中配置。2.配置MAVEN_HOME。在系统变量中新建,变量名MAVEN_HOME,变量值,maven文件夹路径,我的路径是F:\Wab\资料\maven\资料\apache-maven-3.2.3,最好不要有中…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号