2926 - Sub String Rep

Cerința

Se dă numărul natural n și n șiruri de caractere de tip secvență. Determinați pentru fiecare dintre cele n șiruri dacă ele sunt alcătuite prin repetiția a unui subșir de caractere din el. Dacă da se afișează subșirul care a generat secvența sau -1 dacă secvența nu este alcătuită după aceste criterii.

Date de intrare

Programul citește de la tastatură pe primul rând numărul n, iar apoi n șiruri de caractere, pe linii diferite.

Date de ieșire

Programul va afișa pe ecran pe câte un rând secvența cerută sau -1 conform enunțului.

Restricții și precizări

• 1 ≤ n ≤ 1000
• cele n șiruri de caractere citite vor avea maximum 1000 de caractere.

Exemplu 1

Intrare

5

abcabcabc abadabad aabaabaabaab abcdabc jbogzfcfndudqctnqcmzxypuzzlbxcnhddndipjxteakhuzzxlyujoqjncklfzsjdgnlxxjqbjciebhcngyxuohjrsvysoh

Ieșire

abc

abad

aab

-1

-1

Exemplu 2

Intrare

4

abcabcabcab abcdefabcab abababababab abcdefghij

Ieșire

abc

abc

ab

abcdefghij

Rezolvare

#2926 - Sub String Rep
def find_subsequence(s):
    n = len(s)
    for i in range(1, n//2 + 1):
        subsequence = s[:i]
        if subsequence * (n // i) == s:
            return subsequence
    return "-1"

def main():
    n = int(input("Introduceți numărul de șiruri: "))
    for _ in range(n):
        s = input("Introduceți un șir de caractere: ")
        result = find_subsequence(s)
        print(result)

if __name__ == "__main__":
    main()