[codeVS1204] 单词背诵
2024-08-26 11:01:08
题目描述
灵梦有n个单词想要背,但她想通过一篇文章中的一段来记住这些单词。
文章由m个单词构成,她想在文章中找出连续的一段,其中包含最多的她想要背的单词(重复的只算一个)。并且在背诵的单词量尽量多的情况下,还要使选出的文章段落尽量短,这样她就可以用尽量短的时间学习尽可能多的单词了。
输入输出格式
输入格式:
第1行一个数n,
接下来n行每行是一个长度不超过10的字符串,表示一个要背的单词。
接着是一个数m,
然后是m行长度不超过10的字符串,每个表示文章中的一个单词。
输出格式:
输出文件共2行。第1行为文章中最多包含的要背的单词数,第2行表示在文章中包含最多要背单词的最短的连续段的长度。
输入输出样例
输入样例#1:
3
hot
dog
milk
5
hot
dog
dog
milk
hot
输出样例#1:
3
3
说明
【数据范围】
对于30%的数据 n<=50,m<=500;
对于60%的数据 n<=300,m<=5000;
对于100%的数据 n<=1000,m<=100000;
思路
Trie离散化一下,然后先统计一下ans1,ans2通过对离散化和的数组尺取法求出。
代码实现
#include<cstdio>
#include<cstring>
const int maxn=1e3+;
const int maxm=1e5+;
inline int min_(int x,int y){return x<y?x:y;}
int n,m,ans,now,top,map,lng=1e9;
int s[maxm],v[maxn]={};
struct tree{int tn,tp;}t[maxm][];
char ch[];
void add(int k,int i){
if(ch[i]==) return;
int next=ch[i]-'a';
if(!t[k][next].tn) t[k][next].tn=++top;
add(t[k][next].tn,i+);
}
int search(int k,int i){
int next=ch[i]-'a';
if(ch[i]==){
if(!t[k][].tp) t[k][].tp=++map;
return t[k][].tp;
}
if(!t[k][next].tn) return ;
return search(t[k][next].tn,i+);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",ch);
add(,);
}
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%s",ch);
s[i]=search(,);
if(!v[s[i]]) v[s[i]]++,ans++;
}
printf("%d\n",ans);
memset(v,,sizeof(v)),v[]=;
for(int i=,j=;i<=m;i++){
while(now<ans&&j<=m){
if(!v[s[j]]) now++;
v[s[j]]++;
j++;
}
if(now==ans) lng=min_(lng,j-i);
v[s[i]]--;
if(!v[s[i]]) now--;
}
printf("%d\n",lng);
return ;
}
最新文章
- [LeetCode] Compare Version Numbers 版本比较
- 从 datetime2 数据类型到 datetime 数据类型的转换产生一个超出范围的值
- Cadence 建立封装:多个引脚于芯片内部连接的封装建立方式
- 360双击ctrl搜索可能会与firefox快捷键冲突
- varnish中忽略cookie进行缓存
- ibatis CDATA
- js模板引擎实现原理
- WEB程序会话管理--HttpSession和Cookie
- 解决Adobe Acrobat “正在纠偏图像,正在旋转图像,正在分解页面”问题
- Java数组与泛型
- pgadmin3 新建服务器出现错误 Peer authentication failed for user ";postgres"; 的解决办法
- css删除线,下划线等
- for..of与for..in
- Linux系统下rm删除文件后空间没有释放问题解决办法
- 256.Spring Boot+Spring Security: MD5是加密算法吗?
- Unity资源 ----加载最好需要做哪些事
- Gradle构建多模块项目
- 谁记录了mysql error log中的超长信息
- 参数FAST_START_MTTR_TARGET的理解
- 解决使用C/C++配置ODBC链接中文显示为问号(?)的问题
热门文章
- SpringMvc返回@ResponseBody中文乱码
- AndroidStudio中使用SVN
- GeoTools坐标转换(投影转换和仿射变换)
- mysql出错排查
- IntelliJ IDEA openfire 使用IntelliJ IDEA 部署OPENFIRE 服务端
- 51nod 1096 距离之和最小(水题日常)
- 面向对象的设计的SOLID原则
- 世平信息(T 面试)
- 【搜索】P1041 传染病控制
- 连接mysql 2003 Can&#39;t connect to Mysql on &#39;xxx&#39;(10061)