题目链接：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,0,sizeof vis); return ; } inline bool operator < (const Node & other )const { for(int i=0;i<MAXK;i++){ if(vis[i]!=other.vis[i]) return vis[i]<other.vis[i]; } return 0; } }; 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=0;i<n;i++){//枚举所有长度为x的字符串 node.vis[s1[i]-'a']++;//记录子串中出现的字母次数 if(i>=x){//如果超过x那么就要把之前的一个字符删掉，保证字符字符串的长度是x node.vis[s1[i-x]-'a']--; } if(i>=x-1){//如果i>x那么说明长度够x了，就可以往里插了 s.insert(node); } } node.init(); for(int i=0;i<m;i++){ node.vis[s2[i]-'a']++; if(i>=x){ node.vis[s2[i-x]-'a']--; } if(i>=x-1){//长度够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>=0;i--){//枚举的子串的长度 if(ok(i)){ printf("%d ",i); flag=true; break; } } if(flag==false){ puts("0"); } return 0; }