Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Algorithm
5.
Implementation
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Auxiliary Space
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

The Suffix Matches

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

String is one of the most important data structures in perspective to interviews in product-based companies. Advanced concepts related to strings such as suffix tree, Rabin-Karp, suffix arrays are also asked during interviews frequently.

The suffix of a string can be understood as a non-empty substring occurring at the end of the string. Let us solve a problem related to strings and suffixes to increase our understanding of them. Below is the problem statement.

Problem Statement

A string ‘STR’ of size ‘N’ is given. We have to solve ‘Q’ queries, where queries can be defined as follows:

  • IDX: represents a prefix of string ‘STR’ ending at index ‘IDX’. The task is to find the longest matching suffix between string ‘STR’ and the prefix provided by the query.  

Example

Input: STR = “abacdaba”, Q = 3

Queries: 


5

Output: 1 3 0

Explanation: Let us analyze query wise:
Query 1: The prefix ending at index 1 will be “a” where a suffix is also “a”, so the longest matching suffix is of length 1.
Query 2: The prefix ending at index 3 will be “aba” where a suffix is also “aba”, so the longest matching suffix is of length 3.
Query 3: The prefix ending at index 5 will be “abacdaba” for which there is no suffix matching to this prefix. Thus answer is 0.


Input: STR = “wewe”, Q = 2

Queries: 
1
2

Output: 0 2

Explanation: Let us analyze query wise:
Query 1: The prefix ending at index 1 will be “w” for which there is no suffix matching to this prefix. Thus answer is 0.
Query 2: The prefix ending at index 2 will be “we” where a suffix is also “we”, so the longest matching suffix is of length 2.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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!

Previous article
Count triplets with sum smaller than a given value
Next article
Ada String
Live masterclass