Untitled
unknown
plain_text
14 days ago
2.9 kB
2
Indexable
class Trie { Trie[] links; boolean flag; // Marks the end of a word int childCount; // Number of children for the current node public Trie() { links = new Trie[26]; flag = false; childCount = 0; // Initialize child count to 0 } // Check if the current node has a link for the given character boolean containsKey(char ch) { return links[ch - 'a'] != null; } // Add a new Trie node for the given character void put(char ch, Trie newTrie) { links[ch - 'a'] = newTrie; } // Get the Trie node for the given character Trie get(char ch) { return links[ch - 'a']; } // Set the current node as the end of a word void setWordEndFlag() { flag = true; } // Check if the current node marks the end of a word boolean getWordEndFlag() { return flag; } } public class TrieOperations { private Trie root; public TrieOperations() { root = new Trie(); } // Insert a word into the Trie public void insert(String word) { Trie temp = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if (!temp.containsKey(ch)) { temp.put(ch, new Trie()); temp.childCount++; // Increment child count for the current node } temp = temp.get(ch); } temp.setWordEndFlag(); } // Find the length of the Longest Common Prefix (LCP) public int findLongestCommonPrefixLength(String referenceWord) { Trie temp = root; int length = 0; for (int i = 0; i < referenceWord.length(); i++) { char ch = referenceWord.charAt(i); // If the current node has only one child and is not a word-ending node if (temp.childCount == 1 && !temp.getWordEndFlag() && temp.containsKey(ch)) { length++; // Increment the LCP length temp = temp.get(ch); } else { break; // Stop if branching occurs or we reach the end of a common prefix } } return length; } public static void main(String[] args) { TrieOperations trie = new TrieOperations(); // Insert words into the Trie System.out.println("Inserting words: Striver, Striving, String, Strike"); trie.insert("striver"); trie.insert("striving"); trie.insert("string"); trie.insert("strike"); // Use the first inserted word to find the LCP length String referenceWord = "striver"; // Use any word that has been inserted System.out.println("Length of Longest Common Prefix: " + trie.findLongestCommonPrefixLength(referenceWord)); } }
Editor is loading...
Leave a Comment