2016-2017 ACM-ICPC, Asia Tsukuba Regional Contest D Hidden Anagrams
2024-08-25 10:26:59
题目链接:http://codeforces.com/gym/101158/attachments
/*
* @Author: lyucheng
* @Date: 2017-10-21 12:20:04
* @Last Modified by: lyucheng
* @Last Modified time: 2017-10-21 21:12:12
*/
/*
* 题意:给你两个字符串,让你求最长子串,子串在两个字符串中都出现(长度相同,出现的字母次数相同就行)
*
* 思路:枚举每个长度的字符串,加到set中,然后在另一个字符串中查找,枚举长度n,构造长度为x的字符串是n,查找是logn
* 时间复杂度n*n*logn
* */
#include <bits/stdc++.h> #define MAXN 4005
#define MAXK 30 using namespace std; struct Node{
int vis[MAXK];
void init(){
memset(vis,,sizeof vis);
return ;
}
inline bool operator < (const Node & other )const {
for(int i=;i<MAXK;i++){
if(vis[i]!=other.vis[i])
return vis[i]<other.vis[i];
}
return ;
}
};
char s1[MAXN],s2[MAXN];
int n,m;
bool flag=true; bool ok(int x){
Node node;
node.init();
set<Node>s;
for(int i=;i<n;i++){//枚举所有长度为x的字符串
node.vis[s1[i]-'a']++;//记录子串中出现的字母次数
if(i>=x){//如果超过x那么就要把之前的一个字符删掉,保证字符字符串的长度是x
node.vis[s1[i-x]-'a']--;
}
if(i>=x-){//如果i>x那么说明长度够x了,就可以往里插了
s.insert(node);
}
}
node.init();
for(int i=;i<m;i++){
node.vis[s2[i]-'a']++;
if(i>=x){
node.vis[s2[i-x]-'a']--;
}
if(i>=x-){//长度够x了就查找
if(s.find(node)!=s.end())
return true;
}
}
return false;
} void init(){
flag=false;
} int main(){
// freopen("in.txt","r",stdin);
init();
scanf("%s%s",s1,s2);
n=strlen(s1);
m=strlen(s2);
for(int i=n;i>=;i--){//枚举的子串的长度
if(ok(i)){
printf("%d\n",i);
flag=true;
break;
}
}
if(flag==false){
puts("");
}
return ;
}
最新文章
- noip200802排座椅
- 如何为CriteriaOperator过滤对象转换为lambda表达式,即:linq to xpo的动态where语句
- /etc/xinetd.conf 和 /etc/xinetd.d/*【新网络服务配置】
- [game]十字链表的AOI算法实现
- 删除SVN批处理(bat)
- &#39;DEVENV&#39; is not recognized as an internal or external command,
- day18<;集合框架+>;
- 第5章 PCIe总线的事务层
- 详解linux进程间通信-信号
- 腾讯技术分享:微信小程序音视频技术背后的故事
- css瀏覽器私有前綴名
- python HTML报告
- linux安装tomcat及优化
- centos7离线安装rpm包自动解决依赖
- iPhone开发中,关于视图跳转的总结(转)
- Opengl的TOOL收集
- CF815C Karen and Supermarket [树形DP]
- java读取txt文件,对字符串进行操作后导出txt文件
- IM
- 1552: [Cerc2007]robotic sort