Find strings that end with a given suffix

0 0 11 minutes read

Given a set of strings S and a string P, the task is to print all strings from the set with the suffix P. Examples:

Input: S = {“zambiatek”, “zambiatek”, “geek”, “newzambiatek”, “friendsonzambiatek”, “toppergeek”} P = “zambiatek”
Output: zambiatek friendsonzambiatek zambiatek newzambiatek
Input: S = {“wideworld”, “webworld”, “classicword”, “world”, “worldclass”} P = “world”
Output: wideworld webworld world

Approach: The idea is to use Pattern Searching using a Trie of all Suffixes.

Store the strings in a Trie in reverse order.
Reverse the string P and search for it using the standard Trie search algorithm.
Check if the reversed string P is itself a word in Trie, which be checked by seeing if the last matching node has isEndWord flag set.
Otherwise, if the reversed string P forms a suffix, then recursively print all nodes under the subtree of the last matching node.

Below is the implementation of the above approach:

C++

// C++ code to print all
// strings from a given set
// with suffix P
#include <bits/stdc++.h>
using namespace std;
 
#define CHILD (26)
 
// Converts key current character
// into index use only 'a' through
// 'z' and lower case
#define CHAR_TO_INDEX(c) (int)(c - 'a')
 
// Trie node
struct TrieNode {
    struct TrieNode* children[CHILD];
 
    // isWordEnd is true if the node
    // represents end of a word
    bool isWordEnd;
};
 
// Function to reverse a string
string reverseStr(string str)
{
    int n = str.length();
 
    // Swap character starting from
    // two corners
    for (int i = 0; i < n / 2; i++)
        swap(str[i], str[n - i - 1]);
    return str;
}
 
// Returns new trie node
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
    pNode->isWordEnd = false;
 
    for (int i = 0; i < CHILD; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// If not present, inserts key into
// trie. If the key is suffix of trie
// node, just mark leaf node
void insert(struct TrieNode* root,
            const string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int level = 0;
         level < key.length();
         level++) {
 
        int index = CHAR_TO_INDEX(key[level]);
 
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // Mark last node as leaf
    pCrawl->isWordEnd = true;
}
 
// Returns true if key presents in
// the trie, else false
bool search(struct TrieNode* root,
            const string key)
{
    int length = key.length();
    struct TrieNode* pCrawl = root;
    for (int level = 0;
         level < length; level++) {
 
        int index = CHAR_TO_INDEX(key[level]);
 
        if (!pCrawl->children[index])
            return false;
 
        pCrawl = pCrawl->children[index];
    }
 
    return (pCrawl != NULL
            && pCrawl->isWordEnd);
}
 
// Returns 0 if current node has
// a child
// If all children are NULL, return 1
bool isLastNode(struct TrieNode* root)
{
    for (int i = 0; i < CHILD; i++)
        if (root->children[i])
            return 0;
    return 1;
}
 
// Recursive function to print strings
// having given suffix
void printStrings(struct TrieNode* root,
                  string currsuffix)
{
 
    // If a string with currsuffix
    // is found
    if (root->isWordEnd) {
        cout << reverseStr(currsuffix);
        cout << endl;
        reverseStr(currsuffix);
    }
 
    // All children struct node
    // pointers are NULL
    if (isLastNode(root))
        return;
 
    for (int i = 0; i < CHILD; i++) {
        if (root->children[i]) {
 
            // Append current character
            // to currsuffix string
            currsuffix.push_back(97 + i);
 
            // recur over the rest
            printStrings(root->children[i],
                         currsuffix);
            // remove last character
            currsuffix.pop_back();
        }
    }
}
 
// print strings with given suffix
int printStringsWithGivenSuffix(
    TrieNode* root, const string query)
{
    struct TrieNode* pCrawl = root;
 
    // Check if suffix is present
    // and find the node (of last
    // level) with last character
    // of given string.
    int level;
    int n = query.length();
    for (level = 0; level < n;
         level++) {
 
        int index = CHAR_TO_INDEX(query[level]);
 
        // no string in the Trie has
        // this suffix
        if (!pCrawl->children[index])
            return 0;
 
        pCrawl = pCrawl->children[index];
    }
 
    // If suffix is present as a word.
    bool isWord = (pCrawl->isWordEnd
                   == true);
 
    // If suffix is last node of
    // tree (has no children)
    bool isLast = isLastNode(pCrawl);
 
    // If suffix is present as a word,
    // but there is no subtree below
    // the last matching node.
    if (isWord && isLast) {
        cout << query << endl;
        return -1;
    }
 
    // If there are nodes below
    // last matching character.
    if (!isLast) {
        string suffix = query;
        printStrings(pCrawl, suffix);
        return 1;
    }
}
 
// Driver Code
int main()
{
    struct TrieNode* root = getNode();
    vector<string> S
        = { "zambiatek", "zambiatek",
            "geek", "newzambiatek",
            "friendsonzambiatek",
            "toppergeek" };
 
    for (string str : S) {
        insert(root,
               reverseStr(str));
    }
 
    string P = "eek";
 
    printStringsWithGivenSuffix(
        root, reverseStr(P));
 
    return 0;
}

Java

// java code to print all
// strings from a given set
// with suffix P
import java.util.*;
 
public class GFG {
 
  // Converts key current character
  // into index use only 'a' through
  // 'z' and lower case
  static final int CHILD = 26;
 
  // Trie node
  static class TrieNode {
    TrieNode[] children = new TrieNode[CHILD];
    // isWordEnd is true if the node
    // represents end of a word
    boolean isWordEnd;
  }
 
  // Function to reverse a string
  static String reverseStr(String str) {
    int n = str.length();
    char[] chars = str.toCharArray();
    for (int i = 0; i < n / 2; i++) {
      char temp = chars[i];
      chars[i] = chars[n - i - 1];
      chars[n - i - 1] = temp;
    }
    return new String(chars);
  }
 
  // Returns new trie node
  static TrieNode getNode() {
    TrieNode pNode = new TrieNode();
    pNode.isWordEnd = false;
 
    for (int i = 0; i < CHILD; i++)
      pNode.children[i] = null;
 
    return pNode;
  }
 
 
  // If not present, inserts key into
  // trie. If the key is suffix of trie
  // node, just mark leaf node
  static void insert(TrieNode root, String key) {
    TrieNode pCrawl = root;
 
    for (int level = 0; level < key.length(); level++) {
      int index = key.charAt(level) - 'a';
 
      if (pCrawl.children[index] == null)
        pCrawl.children[index] = getNode();
 
      pCrawl = pCrawl.children[index];
    }
 
    // Mark last node as leaf
    pCrawl.isWordEnd = true;
  }
 
 
  // Returns true if key presents in
  // the trie, else false
  static boolean search(TrieNode root, String key) {
    int length = key.length();
    TrieNode pCrawl = root;
    for (int level = 0; level < length; level++) {
      int index = key.charAt(level) - 'a';
 
      if (pCrawl.children[index] == null)
        return false;
 
      pCrawl = pCrawl.children[index];
    }
 
    return (pCrawl != null && pCrawl.isWordEnd);
  }
 
  // Returns 0 if current node has
  // a child
  // If all children are NULL, return 1
  static boolean isLastNode(TrieNode root) {
    for (int i = 0; i < CHILD; i++)
      if (root.children[i] != null)
        return false;
    return true;
  }    
 
  // Recursive function to print strings
  // having given suffix
  static void printStrings(TrieNode root, String currsuffix) {
    if (root.isWordEnd) {
      System.out.println(reverseStr(currsuffix));
      currsuffix = reverseStr(currsuffix);
    }
    if (isLastNode(root))
      return;
 
    for (int i = 0; i < CHILD; i++) {
      if (root.children[i] != null) {
        currsuffix += (char) ('a' + i);
        printStrings(root.children[i], currsuffix);
        currsuffix = currsuffix.substring(0, currsuffix.length() - 1);
      }
    }
  }
 
 
  // check string withg given suffix 
  static int printStringsWithGivenSuffix(TrieNode root, String query) {
    TrieNode pCrawl = root;
 
    // Check if suffix is present
    // and find the node (of last
    // level) with last character
    // of given string.
    int level;
    int n = query.length();
    for (level = 0; level < n; level++) {
      int index = query.charAt(level) - 'a';
      if (pCrawl.children[index] == null)
        return 0;
      pCrawl = pCrawl.children[index];
    }
    boolean isWord = pCrawl.isWordEnd;
    boolean isLast = isLastNode(pCrawl);
    if (isWord && isLast) {
      System.out.println(query);
      return -1;
    }
    if (!isLast) {
      String suffix = query;
      printStrings(pCrawl, suffix);
      return 1;
    }
    return 0;
  }
 
  // Driver code
  public static void main(String[] args) {
    TrieNode root = getNode();
    List<String> S = Arrays.asList("zambiatek", "zambiatek", "geek", "newzambiatek", "friendsonzambiatek", "toppergeek");
 
    for (String str : S) {
      insert(root, reverseStr(str));
    }
 
    String P = "eek";
 
    printStringsWithGivenSuffix(root, reverseStr(P));
  }
}
 
// this code is contributed by bhardwajji

Python

# Python3 code for the above program
class TrieNode(): 
    def __init__(self): 
         
        # Initialize one node for trie 
        self.children = {} 
        self.last = False
 
def reverse(s): 
    str = "" 
    for i in s: 
        str = i + str
    return str
 
class Trie(): 
    def __init__(self): 
         
        # Initialize the trie structure
        self.root = TrieNode() 
        self.word_list = [] 
 
    def formTrie(self, keys): 
         
        # Forms a trie structure
        # with the given set of 
        # strings if it does not
        # exists already else it 
        # merges the key into it
        # by extending the 
        # structure as required 
        for key in keys:
             
            # inserting one key
            # to the trie.
            self.insert(key)  
 
    def insert(self, key): 
         
        # Inserts a key into 
        # trie if it does not 
        # exist already. And if 
        # the key is a suffix
        # of the trie node, just 
        # marks it as leaf node. 
        node = self.root 
 
        for a in list(key): 
            if not node.children.get(a): 
                node.children[a] = TrieNode() 
 
            node = node.children[a] 
 
        node.last = True
 
    def search(self, key): 
         
        # Searches the given key
        # in trie for a full match 
        # and returns True on
        # success else returns False 
        node = self.root 
        found = True
 
        for a in list(key): 
            if not node.children.get(a): 
                found = False
                break
 
            node = node.children[a] 
 
        return node and node.last and found 
 
    def printStrings(self, node, word): 
         
        # Method to recursively
        # traverse the trie 
        # and return a whole word
        if node.last: 
            self.word_list.append(word) 
 
        for a, n in node.children.items(): 
            self.printStrings(n, word + a) 
 
    def printStringsWithGivenSuffix(self, key): 
         
        # Returns all the words in 
        # the trie whose common 
        # suffix is the given key
        # thus listing out all 
        # the strings
        node = self.root 
        not_found = False
        temp_word = '' 
 
        for a in list(key): 
            if not node.children.get(a): 
                not_found = True
                break
 
            temp_word += a 
            node = node.children[a] 
 
        if not_found: 
            return 0
        elif node.last and not node.children: 
            return -1
 
        self.printStrings(node, temp_word) 
 
        for s in self.word_list: 
            print(reverse(s)) 
        return 1
 
# Driver Code 
 
# keys to form the trie structure
keys = [reverse("zambiatek"), 
reverse("zambiatek"), 
reverse("geek"), 
reverse("newzambiatek"), 
reverse("friendsonzambiatek"), 
reverse("toppergeek")] 
 
# key 
key = "eek"
status = ["Not found", "Found"] 
 
# creating trie object 
t = Trie() 
 
# creating the trie structure 
# with the given set of strings
t.formTrie(keys) 
 
# print string having suffix 'P'
# our trie structure
comp = t.printStringsWithGivenSuffix(reverse(key))   

Javascript

// Javascript code to print all
// strings from a given set
// with suffix P
const CHILD = 26;
 
// Converts key current character
// into index use only 'a' through
// 'z' and lower case
const CHAR_TO_INDEX = (c) => c.charCodeAt(0) - 'a'.charCodeAt(0);
 
// Trie node
class TrieNode {
  constructor() {
this.children = Array(CHILD).fill(null);
// isWordEnd is true if the node
// represents end of a word
this.isWordEnd = false;
  }
}
 
// Function to reverse a string
const reverseStr = (str) => str.split('').reverse().join('');
 
// Returns new trie node
const getNode = () => new TrieNode();
 
// If not present, inserts key into
// trie. If the key is suffix of trie
// node, just mark leaf node
const insert = (root, key) => {
  let pCrawl = root;
 
  for (let i = 0; i < key.length; i++) {
const index = CHAR_TO_INDEX(key[i]);
 
if (!pCrawl.children[index]) {
  pCrawl.children[index] = getNode();
}
 
pCrawl = pCrawl.children[index];
  }
 
  // Mark last node as leaf
  pCrawl.isWordEnd = true;
};
 
// Returns true if key presents in
// the trie, else false
const search = (root, key) => {
  const length = key.length;
  let pCrawl = root;
 
  for (let i = 0; i < length; i++) {
const index = CHAR_TO_INDEX(key[i]);
 
if (!pCrawl.children[index]) {
  return false;
}
 
pCrawl = pCrawl.children[index];
  }
 
  return pCrawl !== null && pCrawl.isWordEnd;
};
 
 
// Returns 0 if current node has
// a child
// If all children are NULL, return 1
const isLastNode = (root) => {
  for (let i = 0; i < CHILD; i++) {
if (root.children[i]) {
  return false;
}
  }
  return true;
};
 
// Recursive function to print strings
// having given suffix
const printStrings = (root, currsuffix) => {
  // If a string with currsuffix
  // is found
  if (root.isWordEnd) {
    console.log(reverseStr(currsuffix)+"<br>");
  }
 
 // All children struct node
// pointers are NULL
  if (isLastNode(root)) {
return;
  }
 
  for (let i = 0; i < CHILD; i++) {
if (root.children[i]) {
  // Append current character
  // to currsuffix string
  currsuffix += String.fromCharCode(97 + i);
   
  // recur over the rest
  printStrings(root.children[i], currsuffix);
   
  // remove last character
  currsuffix = currsuffix.slice(0, -1);
}
  }
};
 
// print strings with given suffix
const printStringsWithGivenSuffix = (root, query) => {
  let pCrawl = root;
// Check if suffix is present
// and find the node (of last
// level) with last character
// of given string.
  for (let i = 0; i < query.length; i++) {
const index = CHAR_TO_INDEX(query[i]);
 
// no string in the Trie has
// this suffix
if (!pCrawl.children[index]) {
  return 0;
}
 
pCrawl = pCrawl.children[index];
  }
 
  // If suffix is present as a word.
  const isWord = pCrawl.isWordEnd;
 
  // If suffix is last node of
  // tree (has no children)
  const isLast = isLastNode(pCrawl);
 
  // If suffix is present as a word,
  // but there is no subtree below
  // the last matching node.
  if (isWord && isLast) {
console.log(query+"<br>");
return -1;
  }
 
  // If there are nodes below
  // last matching character.
  if (!isLast) {
let suffix = query;
printStrings(pCrawl, suffix);
return 1;
  }
};
 
// Driver Code
const root = getNode();
const S = [
  'zambiatek',
  'zambiatek',
  'geek',
  'newzambiatek',
  'friendsonzambiatek',
  'toppergeek',
];
 
for (const str of S) {
  insert(root, reverseStr(str));
}
 
const P = 'eek';
printStringsWithGivenSuffix(
        root, reverseStr(P));
         
//This code is contributed by Pushpesh Raj.

C#

// C# program to print all
// strings from a given set
// with suffix P
using System;
using System.Collections.Generic;
 
public class GFG {
    // Converts key current character
    // into index use only 'a' through
    // 'z' and lower case
    const int CHILD = 26;
 
    // Trie node
    class TrieNode {
        public TrieNode[] children = new TrieNode[CHILD];
 
        // isWordEnd is true if the node
        // represents end of a word
        public bool isWordEnd;
    }
    // Function to reverse a string
    static string ReverseStr(string str)
    {
        int n = str.Length;
        char[] chars = str.ToCharArray();
        for (int i = 0; i < n / 2; i++) {
            char temp = chars[i];
            chars[i] = chars[n - i - 1];
            chars[n - i - 1] = temp;
        }
        return new string(chars);
    }
 
    // Returns new trie node
    static TrieNode GetNode()
    {
        TrieNode pNode = new TrieNode();
        pNode.isWordEnd = false;
 
        for (int i = 0; i < CHILD; i++)
            pNode.children[i] = null;
 
        return pNode;
    }
 
    // If not present, inserts key into
    // trie. If the key is suffix of trie
    // node, just mark leaf node
    static void Insert(TrieNode root, string key)
    {
        TrieNode pCrawl = root;
 
        for (int level = 0; level < key.Length; level++) {
            int index = key[level] - 'a';
 
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = GetNode();
 
            pCrawl = pCrawl.children[index];
        }
 
        // Mark last node as leaf
        pCrawl.isWordEnd = true;
    }
 
    // Returns true if key presents in
    // the trie, else false
    static bool Search(TrieNode root, string key)
    {
        int length = key.Length;
        TrieNode pCrawl = root;
        for (int level = 0; level < length; level++) {
            int index = key[level] - 'a';
 
            if (pCrawl.children[index] == null)
                return false;
 
            pCrawl = pCrawl.children[index];
        }
 
        return (pCrawl != null && pCrawl.isWordEnd);
    }
 
    // Returns 0 if current node has
    // a child
    // If all children are NULL, return 1
    static bool IsLastNode(TrieNode root)
    {
        for (int i = 0; i < CHILD; i++)
            if (root.children[i] != null)
                return false;
        return true;
    }
 
    // Recursive function to print strings
    // having given suffix
    static void PrintStrings(TrieNode root,
                             string currsuffix)
    {
        if (root.isWordEnd) {
            Console.WriteLine(ReverseStr(currsuffix));
            currsuffix = ReverseStr(currsuffix);
        }
        if (IsLastNode(root))
            return;
 
        for (int i = 0; i < CHILD; i++) {
            if (root.children[i] != null) {
                currsuffix += (char)('a' + i);
                PrintStrings(root.children[i], currsuffix);
                currsuffix = currsuffix.Substring(
                    0, currsuffix.Length - 1);
            }
        }
    }
 
    // check string withg given suffix
    static int PrintStringsWithGivenSuffix(TrieNode root,
                                           string query)
    {
        TrieNode pCrawl = root;
 
        // Check if suffix is present
        // and find the node (of last
        // level) with last character
        // of given string.
        int level;
        int n = query.Length;
        for (level = 0; level < n; level++) {
            int index = query[level] - 'a';
            if (pCrawl.children[index] == null)
                return 0;
            pCrawl = pCrawl.children[index];
        }
        bool isWord = pCrawl.isWordEnd;
        bool isLast = IsLastNode(pCrawl);
        if (isWord && isLast) {
            Console.WriteLine(query);
            return -1;
        }
        if (!isLast) {
            string suffix = query;
            PrintStrings(pCrawl, suffix);
            return 1;
        }
        return 0;
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        TrieNode root = GetNode();
        List<string> S = new List<string>{
            "zambiatek",    "zambiatek",  "geek",
            "newzambiatek", "friendsonzambiatek", "toppergeek"
        };
 
        foreach(string str in S)
        {
            Insert(root, ReverseStr(str));
        }
 
        string P = "eek";
 
        PrintStringsWithGivenSuffix(root, ReverseStr(P));
    }
}
 
// This code is contributed by Prince kumar

Output:

geek
toppergeek

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!