题目链接: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 ;
}

最新文章

  1. noip200802排座椅
  2. 如何为CriteriaOperator过滤对象转换为lambda表达式,即:linq to xpo的动态where语句
  3. /etc/xinetd.conf 和 /etc/xinetd.d/*【新网络服务配置】
  4. [game]十字链表的AOI算法实现
  5. 删除SVN批处理(bat)
  6. &#39;DEVENV&#39; is not recognized as an internal or external command,
  7. day18&lt;集合框架+&gt;
  8. 第5章 PCIe总线的事务层
  9. 详解linux进程间通信-信号
  10. 腾讯技术分享:微信小程序音视频技术背后的故事
  11. css瀏覽器私有前綴名
  12. python HTML报告
  13. linux安装tomcat及优化
  14. centos7离线安装rpm包自动解决依赖
  15. iPhone开发中,关于视图跳转的总结(转)
  16. Opengl的TOOL收集
  17. CF815C Karen and Supermarket [树形DP]
  18. java读取txt文件,对字符串进行操作后导出txt文件
  19. IM
  20. 1552: [Cerc2007]robotic sort

热门文章

  1. 改用Struts2.5 出现404 错误
  2. session写入memcache
  3. js转换字符串为数值的方法
  4. 1.Bootstrap-简介
  5. Linux入门之常用命令(11) 系统监控 vmstat top
  6. Mybatis Dynamic Query 2.0.2
  7. python之testcenter操作
  8. [转]python单元测试unittest
  9. PHP多进程编之僵尸进程问题
  10. iOS将自己的框架更新到cocopods上