Length of all prefixes that are also the suffixes of given string

Length of all prefixes that are also the suffixes of given string

Given a string S consisting of N characters, the task is to find the length of all prefixes of the given string S that are also suffixes of the same string S.

Examples:

Input: S = “ababababab”
Output: 2 4 6 8
Explanation: 
The prefixes of S that are also its suffixes are:

1. “ab” of length = 2
2. “abab” of length = 4
3. “ababab” of length = 6
4. “abababab” of length = 8

Input: S = “geeksforgeeks”
Output: 5

Naive Approach: The simplest approach to solve the given problem is to traverse the given string, S from the start, and in each iteration add the current character to the prefix string, and check if the prefix string is the same as the suffix of the same length or not. If found to be true, then print the length of the prefix string. Otherwise, check for the next prefix.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h> using namespace std;    void countSamePrefixSuffix(string s, int n) {          string prefix = "";             for (int i = 0; i < n - 1; i++) {                              prefix += s[i];                     string suffix = s.substr(             n - 1 - i, n - 1);                              if (prefix == suffix) {             cout << prefix.size() << " ";         }     } }    int main() {     string S = "ababababab";     int N = S.size();     countSamePrefixSuffix(S, N);        return 0; }

Output:

2 4 6 8

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by using hashing to store the prefixes of the given string. Then, iterate through all the suffixes and check if they are present in the hash map or not. Follow the steps below to solve the problem:

• Initialize two deques, say prefix and suffix to store the prefix string and suffix strings of S.
• Initialize a HashMap, say M to store all the prefixes of S.
• Traverse the given string S over the range [0, N – 2] using the variable i
  • Push the current character at the back of prefix and suffix deque.
  • Mark prefix as true in the HashMap M.
• After the loop, add the last character of the string, say S[N – 1] to the suffix.
• Iterate over the range [0, N – 2] and perform the following steps:
  • Remove the front character of the suffix.
  • Now, check if the current deque is present in the HashMap M or not. If found to be true, then print the size of the deque.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h> using namespace std;    void countSamePrefixSuffix(string s, int n) {          map<deque<char>, int> cnt;             deque<char> prefix, suffix;             for (int i = 0; i < n - 1; i++) {                              prefix.push_back(s[i]);         suffix.push_back(s[i]);                              cnt[prefix] = 1;     }                  suffix.push_back(s[n - 1]);     int index = n - 1;             for (int i = 0; i < n - 1; i++) {                                       suffix.pop_front();                              if (cnt[suffix] == 1) {             cout << index << " ";         }            index--;     } }    int main() {     string S = "ababababab";     int N = S.size();     countSamePrefixSuffix(S, N);        return 0; }

Output:

8 6 4 2

Time Complexity: O(N * log N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets