Algorithm to find all substrings from the given array of string

Question

I need to find all sub-strings from the given array of strings and group them.

Additional condition:

If string S1 contains string S2, S1 contains S3, S2 contains S4 - all them should be in one group.

Example:

Given array: Hello, Hello John, Hi, Hi Bob, Hell, Hi all

Result output:

Group 1: Hello, Hello John, Hell

Group 2: Hi, Hi Bob, Hi All

Answer 1

• Build a trie on the array of strings
• For each array entry, walk the trie and if the current node marks a word, print it (under the same group as the current string). Do some bookkeeping to avoid printing the same word many times.

Time complexity to build the tire is O(|w1| + ... + |wn|) where |wi| is the length of string wi; so it's linear in the sum of the lengths of the strings. Space complexity is bounded by the same expression but is much lower when there's lots of common prefixes (which is what happens in practice).

The query step has time complexity linear in the length of the string---just traverse the branch that corresponds to the string. (Maybe you can mark off strings that you've visited along the way---and are thus prefixed of the current string---so that you won't even traverse them later. Visiting longer strings first helps you bring the time complexity further down.)

Here's a struct to get you started:

typedef struct node_t_ node_t;
struct node_t_ {
    node_t c *children[ALPHABET_SIZE];
    char kIsLeaf; // set to 1 if represents a word
    char ch; // character stored in the leaf (redundant)
}

Inserting is easy. You start with non-NULL root which stores zero character (represents the empty string).

Insertion:

 void insert(const char* str) {
    node_t* current = root;
    while (*str != '\0') {
        if (current->children[*str] == NULL) {
            create new node;
        }
        current = current->children[*str++];
    }
    current->kIsLeaf = 1;
}

The other procedures are very similar. Trie is a very elegant, simple to implement and easy to use data structure.