Untitled

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

    // Search for a word in the Trie
    public boolean search(String word) {
        Trie temp = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!temp.containsKey(ch)) {
                return false;
            }
            temp = temp.get(ch);
        }
        return temp.getWordEndFlag();
    }

    // Check if any word in the Trie starts with the given prefix
    public boolean startsWith(String prefix) {
        Trie temp = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            if (!temp.containsKey(ch)) {
                return false;
            }
            temp = temp.get(ch);
        }
        return true;
    }

    // Find the Longest Common Prefix (LCP) using one of the inserted words
public String findLongestCommonPrefix(String referenceWord) {
    Trie temp = root;
    StringBuilder lcp = new StringBuilder();

    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)) {
            lcp.append(ch);
            temp = temp.get(ch);
        } else {
            break; // Stop if branching occurs or we reach the end of a common prefix
        }
    }

    return lcp.toString();
}
    }

    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");

        // Search for words
        System.out.println("Search if Strawberry exists in Trie: " +
                (trie.search("strawberry") ? "True" : "False"));
        System.out.println("Search if Strike exists in Trie: " +
                (trie.search("strike") ? "True" : "False"));

        // Check for prefix existence
        System.out.println("If words in Trie start with Stri: " +
                (trie.startsWith("stri") ? "True" : "False"));

        // Find Longest Common Prefix
        System.out.println("Longest Common Prefix: " + trie.findLongestCommonPrefix());
    }
}