题目描述

灵梦有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 ;
}

最新文章

  1. [LeetCode] Compare Version Numbers 版本比较
  2. 从 datetime2 数据类型到 datetime 数据类型的转换产生一个超出范围的值
  3. Cadence 建立封装:多个引脚于芯片内部连接的封装建立方式
  4. 360双击ctrl搜索可能会与firefox快捷键冲突
  5. varnish中忽略cookie进行缓存
  6. ibatis CDATA
  7. js模板引擎实现原理
  8. WEB程序会话管理--HttpSession和Cookie
  9. 解决Adobe Acrobat “正在纠偏图像,正在旋转图像,正在分解页面”问题
  10. Java数组与泛型
  11. pgadmin3 新建服务器出现错误 Peer authentication failed for user &quot;postgres&quot; 的解决办法
  12. css删除线,下划线等
  13. for..of与for..in
  14. Linux系统下rm删除文件后空间没有释放问题解决办法
  15. 256.Spring Boot+Spring Security: MD5是加密算法吗?
  16. Unity资源 ----加载最好需要做哪些事
  17. Gradle构建多模块项目
  18. 谁记录了mysql error log中的超长信息
  19. 参数FAST_START_MTTR_TARGET的理解
  20. 解决使用C/C++配置ODBC链接中文显示为问号(?)的问题

热门文章

  1. SpringMvc返回@ResponseBody中文乱码
  2. AndroidStudio中使用SVN
  3. GeoTools坐标转换(投影转换和仿射变换)
  4. mysql出错排查
  5. IntelliJ IDEA openfire 使用IntelliJ IDEA 部署OPENFIRE 服务端
  6. 51nod 1096 距离之和最小(水题日常)
  7. 面向对象的设计的SOLID原则
  8. 世平信息(T 面试)
  9. 【搜索】P1041 传染病控制
  10. 连接mysql 2003 Can&#39;t connect to Mysql on &#39;xxx&#39;(10061)