Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Take away longest prefix of the String which has duplicate substring

[ad_1]

Given a string S of size N, the duty is to take away the longest prefix of the string which has a minimum of one duplicate substring current in S.

Word: The duplicate substring can’t be the prefix itself

Examples: 

Enter: S = “GeeksforGeeks”
Output: “forGeeks”
Clarification: The longest substring which has a replica is “Geeks”.
After deleting this the remaining string turns into “forGeeks”.

Enter: S = “aaaaa”
Output: “a”
Clarification: Right here the longest prefix which has a replica substring is “aaaa”.
So after deleting this the remaining string is “a”. 
Word that the entire string shouldn’t be chosen as a result of then the duplicate string is the prefix itself.

 

Strategy: The issue may be solved based mostly on the next thought:

Discover all of the characters which generally is a start line of a substring which is a replica of the prefix. Then from these factors discover the duplicate of the longest prefix and delete that prefix.

Comply with the illustration beneath for a greater understanding

Illustration:

For instance take S = “aaaaa”

The attainable beginning factors may be at indices 1, 2, 3, 4.

For index 1: The attainable duplicate of the prefix is “aaaa”.
It has size = 4

For index 2: The attainable duplicate of the prefix is “aaa”.
It has size = 3

For index 3: The attainable duplicate of the prefix is “aa”.
It has size = 2

For index 4: The attainable duplicate of the prefix is “a”.
It has size = 1

So take away the prefix of size 4. Due to this fact the string turns into “a”

Comply with the method talked about beneath to unravel the issue:

  • Use two pointers: one to the beginning of the prefix (say i which is 0 initially) and the opposite (say j)to seek out the start line of all attainable duplicate substrings.
  • Iterate j from 1 to N:
    • If S[j] matches S[i] then use a pointer (say okay) and iterate each i and okay to seek out the size of the substring ranging from j which is duplicate of the prefix.
    • Replace the utmost size.
    • Set i once more to 0.
  • Delete the utmost size prefix.

Beneath is the implementation of the above method:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

string delPrefix(string S)

{

    if (S.measurement() == 1)

        return S;

    int i = 0, maxi = 0;

  

    

    

    for (int j = 1; j < S.measurement(); j++) {

        int okay = j;

        whereas (okay < S.measurement() and S[k] == S[i]) {

            okay++;

            i++;

        }

        maxi = max(maxi, i);

        i = 0;

    }

    return S.substr(maxi);

}

  

int most important()

{

    string S = "aaaaa";

    string ans = delPrefix(S);

  

    

    cout << ans;

    return 0;

}

Time Complexity: O(N2)
Auxiliary House: O(1)

[ad_2]

Leave a Reply