To find all the repeating substring in a given string Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of To find all the repeating substring in a given string without wasting too much if your time.

The question is published on by Tutorial Guruji team.

I recetly come across an interview question : To find all the repeating substring in a given string with a minimal size of 2. The algorithm should be efficient one.

Code for above question is given below but it isn’t efficient one.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
#include <string>

using namespace std;

int main()
{
    typedef string::const_iterator iterator;
    string s("ABCFABHYIFAB");
    set<string> found;

    if (2 < s.size())
        for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i)
            for (iterator x = s.begin(); x != i; ++x)
            {
                iterator tmp = mismatch(i, j, x).second;;
                if (tmp - x > 1)
                    found.insert(string(x, tmp));
            }

            copy(found.begin(), found.end(),ostream_iterator<string>(cout, "n"));
}

My question is that, is there any data structure which can implement above question in time complexity of O(N)?

If your answer is Suffix tree or Hashing please elaborate it.

Answer

If you analyze the output for the string "AAAAAAAAAAAAAA", then there are O(n²) characters in it, so the algorithm is at least O(n²).

To achieve O(n²), just build the suffix tree for each suffix of s (indices [1..n], [2..n], [3..n], …, [n..n]). It doesn’t matter if one of the strings has no own end node, just count how often each node is used.

At the end, iterate over each node with count>1 and print its path.

We are here to answer your question about To find all the repeating substring in a given string - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji