Check substring for a given circular string

A string is a sequence of characters. The characters can be the alphabet, symbols, number, alphanumeric, or a combination of all. In this article, I will show you how to check substring for a given circular string. Whether a string is present in the given circular string. Sometimes we tend to think of so complex algorithm for a simple given problem but later we realize it and can be solved easily. So it is normal if you are also facing a similar issue. I will try to solve this problem in a very simple way.

What is a circular string?

Basically, a circular string is a string that does not have a start and endpoint. For example, let a string be “Bhutan” then its circular string will be “B->h->u->t->a->n->B”. I have written the letter ‘B’ at the end of the string mainly to show that after the letter ‘n’ it will be connected to the letter ‘B’.

Let’s show the possible substring for a given circular string. If a circular string is “code”, given below are some of the possible substrings:

deco, co, de, ode, dec, eco, etc…

Algorithm to check whether a substring is present in the given circular string.

For a string to be circular, it can be represented using a sequence of characters in a given string. For example, if a string is “code”, it can be represented as “codecod”, because the longest substring that can be formed using string “code” is “ecod” as the same length of the given string “code”. In this new string, we will iterate over and see if the given substring can be formed.

Pseudocode to check substring for a given circular string.

For writing the code, let’s define what are the input and output.

Input: string x and substring y.

Output: display -1 if y is not present in x else the index of the first letter substring y in the circular string x.

//String x for an input string, n for the size of x.
//String y is substring to check, m for the size of y
Algorithm isSubstring(x, y, n, m){
    for i=0 to n-2 do
        x = x + x[i]
    j=0
    //size is length of the new updated string x
    for i=0 to size-1 do
        if j == m then
            break
        else if x[i] == y[j] then
            j++
        else  then
            j=0
    if j < m then
        return -1
    else then
        return i - j
}

Source code to check substring for the given circular string

The source code given below is written in c++ programming language. The same logic can be implemented using any choice of your programming language.

#include<iostream>
using namespace std;

int isSubstring(string x, string y, int n, int m){
	for(int i=0; i<n-1; i++){
			x.push_back(x[i]);
		}
		int j = 0, size = x.length(), i;
		for(i=0; i<size; i++){
			if(j == m){
				break;
			}else if(x[i] == y[j]){
				j++;
			}else{
				j = 0;
			}
		}
		if(j < m){
			return -1;
		}else{
			return (i - j);
		}
}
int main(){
	string x, y;
	getline(cin, x);
	getline(cin, y);
	cout << isSubstring(x,y, x.length(), y.length()) << endl;
	return 0;
}

Run time complexity of the algorithm

If the size of the string is ‘n’ then the circular substring representation will be n+(n-1). This is approximately 2 times n(i.e, 2n). So the run time is linear.

Therefore the run time to check the substring for the given circular string is O(n).

Conclusion

When we solve the programming question, there will be many ways to solve it. Sometimes we won’t be able to find a simple way to solve it. The reason can be many such as time constraints to solve it. It is okay, given sufficient time to think, you can always find a simple and better way to solve it. Keep practicing to solve more questions, it will improve your analytical thinking, problem-solving, and programming skills. If you like the article, do share, comment, and follow this website.