Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM


You are given a string S and a list L of forbidden words. Our aim is to stepwise delete all the forbidden words from S. In one step we choose a word from L, which is a substring of (the current) S and delete it from S. If there are more candidates to delete we choose the one whose starting index in S is the smallest (if a word from L can be found at several locations, we only delete the earliest occurrence). If there are no more words to delete we get the required string T.


    L=c abc ba
      aaabccbabc → aacbabc → aababc → aabc → a

Input Specification

L1 L2 ... Ln

The first line is the nonempty string S, the next line is the space separated words of L. The number of words in the list is at most 20, with lengths of at most 20. The input data is such that the deleting steps are uniquely determined. All words in the input consists only lowercase English letters.

Output Specification

h T

A single line with the length h of the required string T and the string itself, separated by a space.

Sample Input 1

  1. aaabccbabc
  2. c abc ba
download as text file

Sample Output 1

  1. 1 a
download as text file

Sample Input 2

  1. aaaaccccbaba
  2. a c ba
download as text file

Sample Output 2

  1. 0
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019