The Suffix Matches

Intuition

The above problem can be solved with the help of implementation. We can take the input of string ‘STR’ and start processing queries to solve this problem. To process queries, we can find the longest matching suffix between the string provided by the query and string ‘STR’ by iterating them from backward. The actual algorithm can be understood below.

Algorithm

The algorithm of the above problem is explained below:

• We can take the input of strings ‘STR’ and “Q’ in the main function and then solve each query separately.
• Solving queries, we will implement a function matchingSuffix() to find the longest matching suffix between the provided string in the query and the string ‘STR’.
• In the function matchingSuffix(), we will start iterating from the backward of both strings and will decrease the index until the characters of both the strings are matching. 
• A variable ‘ans’ will count the number of matched characters, which will be equivalent to the longest matching suffix between both the strings. 
• Finally, we will return the value of ans to the main function, and the main function will print the answer.
   

The implementation of the above algorithm is as follows:

Implementation

// Program to find the longest matching suffix.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// Variables to store data.
string STR;
int Q, x, N, ans;

// Function to find the longest matching suffix.
int matchingSuffix(int idx)
{
      // Resetting the value of the answer.
      ans = 0;

      // Iterating through the string to find the longest suffix.
      for (int j = x, k = N - 1; j >= 0 && STR[j] == STR[k]; j--, k--)
            ans++;

      // Returning the final answer.
      return ans;
}

// Main Function.
int main()
{
      // Input for string and number of queries.
      cin >> STR >> Q;

      // Storing the size of the string.
      N = STR.size();

      // Solving the queries.
      for (int i = 0; i < Q; i++)
      {
            cin >> x;
            x--;

            // Printing the answer query wise.
            cout << matchingSuffix(x) << endl;
      }

      // Return value 0.
      return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

abacdaba
3
1 
3 
5

Output

1
3
0

Also see, Euclid GCD Algorithm

Complexity Analysis

Time Complexity

O(N * Q), where ‘N’ is the size of the string ‘STR’ and ‘Q’ is the number of queries.

Explanation
The complexity of the function matchingSuffix() is O(N), as we are trying to iterate through the string ‘STR’ from the back. And we have ‘Q’ queries for which we have to call this function; thus, the final complexity would be O(N * Q).

Auxiliary Space

O(1), i.e., constant space

Explanation
We are not using any extra space for solving the problem; thus, the auxiliary space used is constant, i.e., O(1).

FAQs

1. What is a string?
   A string can be understood as a sequence of characters, where each character has a particular index, and every character is connected to the previous and next character.
    
2. What is the suffix of a string?
   The suffix of a string can be understood as a non-empty substring occurring at the end of the string.
    
3. What is the time complexity of the above algorithm?
   The time complexity of the above algorithm is O(N * Q), where ‘N’ is the size of the string ‘STR’ and ‘Q’ is the number of queries.
    
4. Explain the time complexity of the above algorithm.
   The complexity of the function matchingSuffix() is O(N), as we are trying to iterate through the string ‘STR’ from the back. And we have ‘Q’ queries for which we have to call this function; thus, the final complexity would be O(N * Q).
    
5. What is the space complexity of the above algorithm?
   The auxiliary space used in the above algorithm is O(1) or constant, as we are not using any extra space for solving the problem.

Key Takeaways

The above blog has covered an important and interesting problem related to Data Structures and Algorithms; and strings that help you enhance your problem-solving skills. It also helps us to understand the suffix of strings in a better way.

Check out this problem - Longest Common Prefix

Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!