String subsequence P40306


Statement
 

pdf   zip

html

You are given two strings s and t with respective lengths m and n. Tell if s is a subsequence of t, that is, if there is a subset of m positions of t, 0 ≤ j0 < … < jm−1 < n, such that s[i] = t[ji] for all 0 ≤ i < m. Additionally, tell if there is just one such subset of positions.

Input

Input consists of several cases, each with s and t. You can assume 1 ≤ | s | ≤ | t | ≤ 105, and that the words are made up of only digits and lowercase and uppercase letters.

Output

For every case, tell if there are zero solutions, just one solution, or multiple solutions.

Public test cases
  • Input

    abba bbaa
    abba cacbcbca
    abba dababcbaa
    Z ZZ
    r2d2 c3po
    

    Output

    zero
    one
    multiple
    multiple
    zero
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Catorzè Concurs de Programació de la UPC - Final
    Date
    2016-09-21