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