两个数的二进制表示中的最长公共子串-yiteyi-C++库

给定两个整数n和m。在数字及其十进制值的二进制表示中找到最长的连续子集。例1：

null

Input : n = 10, m = 11Output : 5Explanation : Binary representation of 10 -> 101011 -> 1011longest common substring in both is 101and decimal value of 101 is 5

例2：

Input : n = 8, m = 16Output : 8Explanation : Binary representation of 8  -> 100016 -> 10000longest common substring in both is 1000and decimal value of 1000 is 8

例3：

Input : n = 0, m = 8Output : 9Explanation : Binary representation of 0  -> 08 -> 1000longest common substring in both is 0and decimal value of 0 is 0

问题来源： https://www.geeksforgeeks.org/citrix-interview-experience-set-5-campus/

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

先决条件： 1) substr C++ 2) 查找C++ 我们将给定的数字转换为二进制表示，并将二进制表示存储在两个字符串中。一旦我们得到字符串，我们就可以通过尝试从最大可能长度开始的所有长度的子字符串来找到最长的公共子字符串。

C++

                         // CPP program to find longest contiguous                       
                         // subset in binary representation of given                       
                         // two numbers n and m                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // utility function which returns                       
                         // decimal value of binary representation                       
                         int                                     getDecimal(string s)                       
                         {                       
                                                 int                                     len = s.length();                       
                                                 int                                     ans = 0;                       
                                                 int                                     j = 0;                       
                                                 for                                     (                                     int                                     i = len - 1; i >= 0; i--)                       
                                                 {                       
                                                 if                                     (s[i] ==                                     '1'                                     )                       
                                                 ans +=                                     pow                                     (2, j);                       
                                                 j += 1;                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Utility function which convert decimal                       
                         // number to its binary representation                       
                         string convertToBinary(                                     int                                     n)                       
                         {                       
                                                 string temp;                       
                                                 while                                     (n > 0)                       
                                                 {                       
                                                 int                                     rem = n % 2;                       
                                                 temp.push_back(48 + rem);                       
                                                 n = n / 2;                       
                                                 }                       
                                                 reverse(temp.begin(), temp.end());                       
                                                 return                                     temp;                       
                         }                       
           
                         // utility function to check all the                       
                         // substrings and get the longest substring.                       
                         int                                     longestCommon(                                     int                                     n,                                     int                                     m)                       
                         {                       
                                                 int                                     mx = -INT_MAX;                                     // maximum length                       
                                                 string s1 = convertToBinary(n);                       
                                                 string s2 = convertToBinary(m);                       
           
                                                 string res;                                     // final resultant string                       
                                                 int                                     len = s1.length();                       
                                                 int                                     l = len;                       
           
                                                 // for every substring of s1,                       
                                                 // check if its length is greater than                       
                                                 // previously found string                       
                                                 // and also it is present in string s2                       
                                                 while                                     (len > 0)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < l - len + 1; i++)                       
                                                 {                       
                                                 string temp = s1.substr(i, len);                       
           
                                                 int                                     tlen = temp.length();                       
                                                 if                                     (tlen > mx && s2.find(temp) != string::npos)                       
                                                 {                       
                                                 res = temp;                       
                                                 mx = tlen;                       
                                                 }                       
                                                 }                       
                                                 len = len - 1;                       
                                                 }                       
           
                                                 // If there is no common string                       
                                                 if                                     (res ==                                     ""                                     )                       
                                                 return                                     -1;                       
           
                                                 return                                     getDecimal(res);                       
                         }                       
           
                         // driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10, m = 11;                       
                                                 cout <<                                     "longest common decimal value : "                       
                                                 << longestCommon(m, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find longest contiguous                       
                         // subset in binary representation of given                       
                         // two numbers n and m                       
                         public                                     class                                     GFG                       
                         {                       
                                                 // utility function to check all the                       
                                                 // substrings and get the longest substring.                       
                                                 static                                     int                                     longestCommon(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 int                                     mx = -Integer.MAX_VALUE;                                     // maximum length                       
                                                 String s1 = Integer.toBinaryString(n);                       
                                                 String s2 = Integer.toBinaryString(m);                       
                                   
                                                 String res =                                     null                                     ;                                     // final resultant string                       
                                                 int                                     len = s1.length();                       
                                                 int                                     l = len;                       
                                   
                                                 // for every substring of s1,                       
                                                 // check if its length is greater than                       
                                                 // previously found string                       
                                                 // and also it is present in string s2                       
                                                 while                                     (len >                                     0                                     )                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < l - len +                                     1                                     ; i++)                       
                                                 {                       
                                                 String temp = s1.substring(i, i + len);                       
                                   
                                                 int                                     tlen = temp.length();                       
                                                 if                                     (tlen > mx && s2.contains(temp))                       
                                                 {                       
                                                 res = temp;                       
                                                 mx = tlen;                       
                                                 }                       
                                                 }                       
                                   
                                                 len = len -                                     1                                     ;                       
                                                 }                       
                                   
                                                 // If there is no common string                       
                                                 if                                     (res ==                                     ""                                     )                       
                                                 return                                     -                                     1                                     ;                       
                                   
                                                 return                                     Integer.parseInt(res,                                     2                                     );                       
                                                 }                       
                                   
                                                 // driver program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     10                                     ;                       
                                                 int                                     m =                                     11                                     ;                       
                                                 System.out.println(                                     "Longest common decimal value : "                       
                                                 +longestCommon(m, n));                       
                                                 }                       
                         }                       
           
                         // This code is Contributed by Sumit Ghosh                       

Python3

                         # Python3 program to find longest contiguous                       
                         # subset in binary representation of given                       
                         # two numbers n and m                       
           
                         # utility function which returns                       
                         # decimal value of binary representation                       
                         def                                     getDecimal(s):                       
                                                 lenn                                     =                                     len                                     (s)                       
                                                 ans                                     =                                     0                       
                                                 j                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (lenn                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 if                                     (s[i]                                     =                                     =                                     '1'                                     ):                       
                                                 ans                                     +                                     =                                     pow                                     (                                     2                                     , j)                       
                                                 j                                     +                                     =                                     1                       
                                                 return                                     ans                       
           
                         # Utility function which convert decimal                       
                         # number to its binary representation                       
                         def                                     convertToBinary(n):                       
           
                                                 return                                     bin                                     (n)[                                     2                                     :]                       
           
                         # utility function to check all the                       
                         # substrings and get the longest substring.                       
                         def                                     longestCommon(n, m):                       
                                                 mx                                     =                                     -                                     10                                     *                                     *                                     9                                     # maximum length                       
                                                 s1                                     =                                     convertToBinary(n)                       
                                                 s2                                     =                                     convertToBinary(m)                       
                                                 #print(s1,s2)                       
           
                                                 res                                     =                                     ""                                     # final resultant string                       
                                                 lenn                                     =                                     len                                     (s1)                       
                                                 l                                     =                                     lenn                       
           
                                                 # for every subof s1,                       
                                                 # check if its length is greater than                       
                                                 # previously found string                       
                                                 # and also it is present in s2                       
                                                 while                                     (lenn >                                     0                                     ):                       
           
                                                 for                                     i                                     in                                     range                                     (l                                     -                                     lenn                                     +                                     1                                     ):                       
           
                                                 temp                                     =                                     s1[i:lenn                                     +                                     1                                     ]                       
                                                 # print(temp)                       
           
                                                 tlenn                                     =                                     len                                     (temp)                       
           
                                                 if                                     (tlenn > mx                                     and                                     ( s2.find(temp) !                                     =                                     -                                     1                                     )):                       
                                                 res                                     =                                     temp                       
                                                 mx                                     =                                     tlenn                       
           
                                                 lenn                                     =                                     lenn                                     -                                     1                       
           
                                                 # If there is no common string                       
                                                 if                                     (res                                     =                                     =                                     ""):                       
                                                 return                                     -                                     1                       
           
                                                 return                                     getDecimal(res)                       
           
                         # Driver Code                       
                         n                                     =                                     10                       
                         m                                     =                                     11                       
                         print                                     (                                     "longest common decimal value : "                                     ,                       
                                                 longestCommon(m, n))                       
           
                         # This code is contributed by Mohit Kumar                       

C#

                         // C# program to find longest contiguous                       
                         // subset in binary representation of given                       
                         // two numbers n and m                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                                 // utility function to check all the                       
                                                 // substrings and get the longest substring.                       
                                                 static                                     int                                     longestCommon(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 int                                     mx = -                                     int                                     .MaxValue;                                     // maximum length                       
                                                 String s1 = Convert.ToString(n, 2);                       
                                                 String s2 = Convert.ToString(m, 2);;                       
                                   
                                                 String res =                                     null                                     ;                                     // final resultant string                       
                                                 int                                     len = s1.Length;                       
                                                 int                                     l = len;                       
                                   
                                                 // for every substring of s1,                       
                                                 // check if its length is greater than                       
                                                 // previously found string                       
                                                 // and also it is present in string s2                       
                                                 while                                     (len > 0)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < l - len + 1; i++)                       
                                                 {                       
                                                 String temp = s1.Substring(i, len);                       
                                   
                                                 int                                     tlen = temp.Length;                       
                                                 if                                     (tlen > mx && s2.Contains(temp))                       
                                                 {                       
                                                 res = temp;                       
                                                 mx = tlen;                       
                                                 }                       
                                                 }                       
                                   
                                                 len = len - 1;                       
                                                 }                       
                                   
                                                 // If there is no common string                       
                                                 if                                     (res ==                                     ""                                     )                       
                                                 return                                     -1;                       
                                   
                                                 return                                     Convert.ToInt32(res, 2);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     n = 10;                       
                                                 int                                     m = 11;                       
                                                 Console.WriteLine(                                     "Longest common decimal value : "                       
                                                 +longestCommon(m, n));                       
                                                 }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // JavaScript program to find longest contiguous                       
                         // subset in binary representation of given                       
                         // two numbers n and m                       
                                   
                                                 // utility function to check all the                       
                                                 // substrings and get the longest substring.                       
                                                 function                                     longestCommon(n,m)                       
                                                 {                       
                                                 let mx = -Number.MAX_VALUE;                                     // maximum length                       
                                                 let s1 = (n >>> 0).toString(2);                       
                                                 let s2 = (m >>> 0).toString(2);                       
                                   
                                                 let res =                                     null                                     ;                                     // final resultant string                       
                                                 let len = s1.length;                       
                                                 let l = len;                       
                                   
                                                 // for every substring of s1,                       
                                                 // check if its length is greater than                       
                                                 // previously found string                       
                                                 // and also it is present in string s2                       
                                                 while                                     (len > 0)                       
                                                 {                       
                                                 for                                     (let i = 0; i < l - len + 1; i++)                       
                                                 {                       
                                                 let temp = s1.substring(i, i + len);                       
                                   
                                                 let tlen = temp.length;                       
                                                 if                                     (tlen > mx && s2.includes(temp))                       
                                                 {                       
                                                 res = temp;                       
                                                 mx = tlen;                       
                                                 }                       
                                                 }                       
                                   
                                                 len = len - 1;                       
                                                 }                       
                                   
                                                 // If there is no common string                       
                                                 if                                     (res ==                                     ""                                     )                       
                                                 return                                     -1;                       
                                   
                                                 return                                     parseInt(res, 2);                       
                                                 }                       
                                   
                                                 // driver program to test above function                       
                                                 let n = 10;                       
                                                 let m = 11;                       
                                                 document.write(                                     "Longest common decimal value : "                       
                                                 +longestCommon(m, n));                       
                                   
           
           
                         // This code is contributed by unknown2108                       
           
                         </script>                       

输出：

longest common decimal value : 5

对上述方法的优化： 上述解决方案可以通过以下帖子中讨论的方法进行优化：动态规划|集29（最长公共子串）本文由 曼迪星 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章