You are not logged in. Please login at www.codechef.com to post your questions!

×

STEM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra

DIFFICULTY:

Easy

PREREQUISITES:

Strings, In-built data structures, Hashmaps

PROBLEM:

Given $N$ words, find the longest such word which is common to all of them.

EXPLANATION:

The first things to note are that the length of all the words is $\leq 20$ and there can be a maximum of 10 words. Let the longest word in the given set of words be of length $L$. Thus, the total number of distinct substrings we can get from this word is $\mathcal{O}(L^2)$. Accordingly, the total number of distinct substrings that we can get from the set of words is $\mathcal{O}(NL^2)$.

Once, we have a list of all the distinct substrings, we just need, for each word, the number of words which it appears in. If it appears in all the $N$ words, then it can be a potential candidate for our answer.

How do we implement this? We can use an in-built implementation of hashmap that is available in the language you are using. The hashmap will be organised as $ map< key,\, list> $. The $keys$ here are the distinct substrings from the given set of strings. For each $key$, we store a list of indices of words which it appears in. We can build this structure by taking one word at a time (say the $i^{th}$ word) examining each its substrings, and putting inserting $i$ in the list associated with the substrings in our map. The word can contain a same substring twice. For example, $anan$ contains $an$ twice. Thus, we have to make sure that we dont insert $i$ twice into the list of a substring which appears twice in it.

Here is the pseudocode:

func get_stem(words [])
{
        for (i = 1 to N in words)
        {
                for (all substrings `subs' of words[i])
                {
                        if(map[subs].insert doesn't contain i)
                                map[subs].insert(i);
                }
        }

    for(all keys `k' in the map)
            if(k = longest and lexicographically smallest word with associated list of size = N)
                    return k;

}

COMPLEXITY:

$\mathcal{O}(NL^3\log (NL^2))$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 17 Oct '15, 01:12

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 09 Feb '16, 16:42

admin's gravatar image

0★admin ♦♦
19.8k350498541

I am getting "Access Denied" errors when trying to view solutions. Please make the solutions public as soon as possible. Thanks!

(19 Oct '15, 00:03) noble_mushtak5★

skysarthak fails for the test case

1 3 ab ba b

raj_ankit744 needs a step of the form

if (f[0] == 0 || strcmp(ch,f)<0) strcpy(f,ch);

link

answered 19 Oct '15, 03:44

john_smith_3's gravatar image

6★john_smith_3
59517
accept rate: 26%

Why am I getting WA ..my solution is https://www.codechef.com/viewsolution/8583271.. please help me. thanks.

link

answered 19 Oct '15, 00:28

raj_ankit744's gravatar image

4★raj_ankit744
1
accept rate: 0%

Can someone please help me identify the cases for which my code fails Link

link

answered 19 Oct '15, 01:26

skysarthak's gravatar image

3★skysarthak
453
accept rate: 0%

Any idea why this https://www.codechef.com/viewsolution/8579208, is giving WA?

Any testcase will be helpful. Have tried out multiple testcases but haven't found any failure pattern yet. Thanks

link

answered 19 Oct '15, 14:32

slakshmi_ms's gravatar image

3★slakshmi_ms
1
accept rate: 0%

My approach:

  • Pick a reference string. Ideally the shortest but assuming malevolent test cases that's not too important.
  • Test the single characters for appearance in the other strings.
  • repeat over increasing string lengths until finding no longer strings:
    • where two consecutive positions succeeded in the previous round, test in the other strings for appearance of the one-longer string that they covered together. (e.g. having found asdf and sdfg, test for asdfg)
  • Collect the set of longest strings and sort for the answer.

my submission

link

answered 18 Aug '18, 10:42

joffan's gravatar image

5★joffan
9488
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×3,746
×349
×53
×5
×1

question asked: 17 Oct '15, 01:12

question was seen: 4,444 times

last updated: 18 Aug '18, 10:42