Find Set

5

3 votes
Algorithms, String Searching, String Algorithms, C++
Problem

You are given a set of N strings. Your task is to determine the minimum possible size of set S (S is a subset of N strings) such that it meets the following conditions:

  • All N strings must be covered by set S
  • A string P is said to be covered by the set S if either P exists in S or any substring of P exists in S.

Input Format:

  • First line contains an integer N
  • Next N lines contains a string P

Output Format:

Print the minimum possible size of set S , which covers all the N strings.

Constraints:

1N5001|P|500

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • S should contain following strings:
    • test
    • earth
    • string
  • |S|=3
Editor Image

?