Battle Dev RegionsJob - Mars 2019 : Exercice 6/6 : Extrémités manquantes

battle_dev_regionsjob_201903_extremites_manquantes.py

"""
Test from here : https://www.isograd.com/FR/solutionconcours.php?contest_id=46
"""

#*******
#* Read input from STDIN
#* Use: echo or print to output your result to STDOUT, use the /n constant at the end of each result line.
#* Use: sys.stderr.write() to display debugging information to STDERR
#* ***/
import sys

lines = []
for line in sys.stdin:
	lines.append(line.rstrip('\n'))

"""
Énoncé

Vous avez essayé de réparer votre clavier défectueux (cf. avant-dernier exercice), mais le résultat vous laisse perplexe. Il manque toujours des lettres dans vos textes ; de plus, il semble y avoir un phénomène mystérieux impliquant la barre d'espace, puisque ces lettres manquantes sont désormais concentrées au début et à la fin des mots ! Vous vous êtes donc résolu(e) à appuyer très peu sur Espace et à former de longues suites de lettres contiguës.

Objectif

Encore une fois, la question est de connaître les ambiguïtés susceptibles d'apparaître. Étant donnée plusieurs chaînes de caractères, on cherche la plus longue chaîne qui pourrait être obtenue à partir de toutes les chaînes en entrée par suppression de lettres en début et/ou en fin de chaîne.

Dans cet exercice on vous donnera toujours deux chaînes en entrée. Par contre la longueur de chaque chaîne peut être élevée, n'essayez donc pas d'employer un algorithme naïf. Une complexité en temps quasi-linéaire est attendue.

Données

Entrée

Ligne 1 : un entier N entre 2 et 50000, le nombre de lettres de chaque chaîne.
Lignes 2 et 3 : sur chaque ligne, une chaîne de N caractères constituée uniquement des 26 lettres de l'alphabet en minuscule.

Sortie

Un entier, indiquant la longueur maximale d'une chaîne de caractères qui pourrait être obtenue à partir des mots en entrée, en supprimant des caractères au début et/ou à la fin de ceux-ci.

Exemple

7
bonjour
abonnes

La réponse attendue est 3.
Cela correspond à la chaîne bon, qui peut être obtenue tout aussi bien à partir de bonjour (suppression des 4 derniers caractères) qu'à partir d'abonnes (on enlève la première lettre et les trois dernières).
"""

def substrings(string, size):
    nmk = len(string) - size
    for i in range(size + 1):
        yield string[i:i + nmk]


def find_longest_common_substring(strings):
    assert len(set(map(len, strings))) == 1

    tested_subs = {}
    for size in range(len(strings[0])):
        tested_subs[size] = []
        for i, string in enumerate(strings):
            for sub in substrings(string, size):
                if sub not in tested_subs[size]:
                    tested_subs[size].append(sub)
                    if all(sub in other for other in strings[:i] + strings[i+1:]):
                        return sub


strings = lines[1:]
sub = find_longest_common_substring(strings)
print(str(len(sub)), sub, file=sys.stderr)
print(str(len(sub)))