Longest prefix matching

Longest prefix match refers to an algorithm used by routers in Internet Protocol (IP) networking to select an entry from forwarding table.

Write a program to implement longest prefix match using trie?

Algorithm Explanation

	Pass strings array and word to longest prefix match utility function. Find length of the input string and Initialize reference to traverse through Trie
	Iterate through all characters of input string ‘str’ and traverse down the Trie.
	Find current character of str and HashMap of current Trie node to traverse down. if there is a Trie edge for the current character, update the list.
	If this is end of a word, then update prevMatch. If the last processed character did not match end of a word, return the previously matching prefix.
	Return the Matching prefix string and display the value.

Source Code

package com.dsacode.DataStructre.trie;
 
import java.util.Arrays;
import java.util.HashMap;
 
class TrieNodeLong {
    public char value;   
    private HashMap < Character, TrieNodeLong > children;
    public boolean bIsEnd;
     
    public TrieNodeLong(char ch)  {
        value = ch;
        children = new HashMap < Character, TrieNodeLong >();
        bIsEnd = false;
    }
     
    public HashMap < Character, TrieNodeLong > getChildren() {  
        return children; 
    }
     
    public TrieNodeLong getChildren(int i) {  
        return children.get(i); 
    }
     
}
 
public class LongestPrefix {
    private TrieNodeLong root;
     
    public LongestPrefix(){    
        root = new TrieNodeLong((char)0);      
    }   
    
     
    public void insert(String word)  {
        int length = word.length();       
        TrieNodeLong crawl = root;
            
        for( int level = 0; level < length; level++) {
            HashMap < Character, TrieNodeLong > child = crawl.getChildren();           
            char ch = word.charAt(level);
 
            if( child.containsKey(ch)){
                crawl = child.get(ch);
            }else{             
                TrieNodeLong temp = new TrieNodeLong(ch);
                child.put( ch, temp );
                crawl = temp;
            }
        }
            
        crawl.bIsEnd = true;
    }
        
    public String getMatchingPrefix(String input)  {
        String result = "";
        int length = input.length();        
        TrieNodeLong crawl = root;  
           
        int level, prevMatch = 0;
        for( level = 0 ; level < length; level++ ) {   
            char ch = input.charAt(level);   
            HashMap < Character, TrieNodeLong > child = crawl.getChildren();                       
            if( child.containsKey(ch) )  {
               result += ch;         
               crawl = child.get(ch);
               if( crawl.bIsEnd )
                    prevMatch = level + 1;
            }           
            else 
                break;
        }
           
        if( !crawl.bIsEnd )
                return result.substring(0, prevMatch);       
          
        else
            return result;
    }
        
   
     
    public static void main(String[] args) {
        LongestPrefix dict = new LongestPrefix();
        String []arr = {"are","area","base","cat","cater","basement"};
         
        for(String str : arr)
            dict.insert(str);
        System.out.println("All the strings from arrays: "+ Arrays.toString(arr));
        System.out.println();
 
        String input = "caterer";
        System.out.println("Search Matching prefix '"+ input+"' from given words: "+ dict.getMatchingPrefix(input));             
      
        input = "basement";
        System.out.println("Search Matching prefix '"+ input+"' from given words: "+ dict.getMatchingPrefix(input));
         
        input = "arex";
        System.out.println("Search Matching prefix '"+ input+"' from given words: "+ dict.getMatchingPrefix(input));
         
        input = "basemexz";
        System.out.println("Search Matching prefix '"+ input+"' from given words: "+ dict.getMatchingPrefix(input));
 
    }
 
}

Output

All the strings from arrays: [are, area, base, cat, cater, basement]
 
Search Matching prefix 'caterer' from given words: cater
Search Matching prefix 'basement' from given words: basement
Search Matching prefix 'arex' from given words: are
Search Matching prefix 'basemexz' from given words: base