-1

How to check if two strings have any common part (sub-string) in c++.

I thought of sorting the strings and then using loops on both the strings to check if they have a common part. But I am not sure. And I also thought that this would not be the optimal strategy for the question

Consider strings - 'batman' and 'catman' They have a common part 'atman'.

P.S. I am not checking for more than one characters. eg - 'apple' and 'batman' have a in common but I am interested in sub-string (min. two common consecutive characters).

Anant Mathur
  • 13
  • 1
  • 10
  • I suppose you mean the LCS algorithm (https://en.wikipedia.org/wiki/Longest_common_substring_problem). To my knowledge there is no stock implementation. – gast128 Feb 04 '19 at 10:35
  • Sorting and then checking for common letters only check for common letters, not sub-strings. For example, consider e.g. `"batman"` and `"manbat"`. If you sort the letters then the strings would be considered totally equal. – Some programmer dude Feb 04 '19 at 10:36
  • Google's [diff-match-patch](https://github.com/google/diff-match-patch) works well for this. Get diffs between two strings, filter for equal stretches. – Amadan Feb 04 '19 at 10:37
  • I have to solve this using sorting and searching techniques only. – Anant Mathur Feb 04 '19 at 10:37
  • 4
    If you have any specific requirements or limitations, those should really be part of the actual question. Please take some time to review [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Feb 04 '19 at 10:39
  • 1
    check this https://stackoverflow.com/questions/10248728/how-to-find-longest-common-substring-using-c – Equation Solver Feb 04 '19 at 10:44
  • @Someprogrammerdude A substring of length one is still a substring. Perhaps one wants to find a longest common substring, or a longest common subsequence, or something like that. – n. m. could be an AI Feb 04 '19 at 10:50
  • If you want to find a common two character substring, consider sorting all two character substrings of each string. – n. m. could be an AI Feb 04 '19 at 10:52
  • @EquationSolver a subsequence is not a substring. Two totally different problems. – n. m. could be an AI Feb 04 '19 at 10:53
  • Have you performed any research? Made any attempts? Or were we your first port of call? – Lightness Races in Orbit Feb 04 '19 at 11:23

3 Answers3

0

This might not be the most efficient code, but so you can get an idea of how it would work in the batman and catman case:

Note: This does solve other cases like "batmanuc" and "catmanic", which would be "atman".

It is not perfect nor the most efficient, but it can help you understand a way to do it and how to manage positions of arrays. From here, implementing it in your own way and adding details is up to you!

like if max>2then print the array, if not, dont print it, for example. 

   #include <iostream>

    using namespace std;

    int main()
    {
        char arr1[10]="batmanuc";
        char arr2[10]="catmanic";
        char common[10];
        int cont=0;
        int max=0;
        for (int i=0;i<10;i++){
            if(arr1[i]==arr2[i]){
                if(cont==max){
                common[cont]=arr1[i];
                cont++;
                max++;
                }
            }
            else cont=0;

        }

        printf("%s",common);
        return 0;
}
M.K
  • 1,464
  • 2
  • 24
  • 46
0

This function will give you the longest common substring of two strings: (Probably not the fastest way you would do it)

std::string GetLongestCommonSubstring(std::string const& a, std::string const& b) {
    std::vector<std::string> substrings;
    for (auto beg = a.begin(); beg != std::prev(a.end()); ++beg)
        for (auto end = beg; end != a.end(); ++end)
            if (b.find(std::string(beg, std::next(end))) != std::string::npos)
                substrings.emplace_back(beg, std::next(end));
    return *std::max_element(substrings.begin(), substrings.end(), 
           [](auto& elem1, auto& elem2) { return elem1.length() < elem2.length(); });
}

Example:

int main() {
    std::cout << GetLongestCommonSubstring("batman", "catman") << std::endl;
}

Output:

atman

Ruks
  • 3,886
  • 1
  • 10
  • 22
0

A stupid algorithm - for each window size from a maximum window (equal to the max of string lengths) to minimum window size (equal to 2, stated in the question), for each position in both strings compare each position with each position in both string with each window_size.

#include <iostream>
#include <string>
#include <cstring>
#include <cassert>
#include <cstdio>

std::string find_common_part(std::string one, std::string two) {
    const auto onesize = one.size();
    const auto twosize = two.size();
    const auto onebegin = one.begin();
    const auto twobegin = two.begin();
    // min. two common consecutive characters
    for (std::size_t window_size = std::max(onesize, twosize);
            window_size >= 2;
            --window_size) {
        for (auto onepos = onebegin, 
                oneposmax = onebegin + (onesize - window_size);
                onepos <= oneposmax;
                ++onepos) {
            for (auto twopos = twobegin, 
                    twoposmax = twobegin + (twosize - window_size);
                    twopos <= twoposmax; 
                    ++twopos) {
                if (std::equal(onepos, onepos + window_size, twopos)) {
                    return std::string(onepos, onepos +  window_size);
                }
            }
        }
    }
    return std::string();
}

int main()
{
    std::cout << find_common_part("catman", "batman") << std::endl;
    assert(find_common_part("catman", "batman") == "atman");
    assert(find_common_part("batman", "manbat") == "man" || 
        find_common_part("batman", "manbat") == "bat");
    return 0;
}
KamilCuk
  • 120,984
  • 8
  • 59
  • 111