Cod sursa(job #3265382)

Utilizator Mirc100Mircea Octavian Mirc100 Data 29 decembrie 2024 19:57:39
Problema ADN Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 3.28 kb
def kmp(  p):
    n = len(p)
    pi = [0] * n
    q = 0
    for i in range(1, n):
        while q > 0 and p[i] != p[q]:
            q = pi[q - 1]
        if p[i] == p[q]:
            q = q + 1
        pi[i] = q
    return pi

def suprapunere(  s, p, pi, m):
    n = len(s)
    q = 0

    for i in range(1, n):
        while q > 0 and s[i] != p[q]:
            q = pi[q - 1]
        if s[i] == p[q]:
            q = q + 1
        if q == m:
            q += 1
    return q

"""def suprapunere(self,a,b):
    for i in range(len(b)-1,-1,-1):
        if a[-i-1:]==b[:i+1]:
            return i+1
    return 0
"""

def get_traseu(  poz, x, pred):
    traseu = []
    while poz != -1:
        traseu.append(poz)
        x_nou = x ^ (1 << poz)
        poz = pred[poz][x]
        x = x_nou
    return traseu

def afis_traseu(  poz, x, suprapunere, pred, secv, cost):
    t = get_traseu(poz, x, pred)

    rez = ""
    for i in range(len(t) - 1, 0, -1):
        # print(secv[t[i]])
        suprapunere = cost[t[i]][t[i - 1]]
        de_afisat = len(secv[t[i]]) - suprapunere
        rez += secv[t[i]][:de_afisat]
    rez += secv[t[0]]
    return rez

"""        
def afis_traseu(self,poz,x,suprapunere,pred,secv,cost):
        if poz!=-1:
            de_afisat=len(secv[poz])-suprapunere
            return self.afis_traseu(pred[poz][x],x^(1<<poz),cost[pred[poz][x]][poz],pred,secv,cost)+secv[poz][:de_afisat]
            #print(secv[poz],poz,suprapunere)
        else:
            return ""
"""

def shortestSuperstring(words )  :
    secv = words
    n = len(secv)
    cost = [[0 for i in range(len(secv))] for i in range(len(secv))]

    for i in range(len(secv)):
        m = len(secv[i])
        pi =  kmp(secv[i])
        for j in range(len(secv)):
            if i != j:
                cost[j][i] = suprapunere(secv[j], secv[i], pi, m)
    # print(*cost,sep="\n")

    nr_submult = 1 << n
    inf = -1
    dp = [[inf for i in range(nr_submult)] for j in range(n)]
    pred = [[-1 for i in range(nr_submult)] for j in range(n)]
    for i in range(n):
        dp[i][1 << i] = 0

    for x in range(1, nr_submult):  # toate sumbultimile nevide
        for i in range(n):
            if x & (1 << i):
                for j in range(n):  # vecinii  lui i
                    if j != i and (x & (1 << j) != 0) and dp[j][x ^ (1 << i)] != inf:  # (j este in S)
                        if dp[i][x] < dp[j][x ^ (1 << i)] + cost[j][i]:
                            dp[i][x] = dp[j][x ^ (1 << i)] + cost[j][i]
                            pred[i][x] = j
    cost_max = -1
    poz_max = None
    for i in range(n):
        if dp[i][nr_submult - 1] != inf and dp[i][nr_submult - 1] > cost_max:
            cost_max = dp[i][nr_submult - 1]
            poz_max = i

    return afis_traseu(poz_max, nr_submult - 1, 0, pred, secv, cost)
f=open("adn.in")
n=int(f.readline())
secv_init=[linie.strip("\n") for linie in f]
f.close()
#print(secv_init)
secv=[]
#eliminare siruri care sunt unul prefixul celuilalt
for i in range(len(secv_init)):
    for j in range(len(secv_init)):
        if j!=i and (secv_init[i] in secv_init[j]):
            break
    else:
        secv.append(secv_init[i])

secv_init.clear()
g=open("adn.out","w")
s="abc"
g.write(s)
g.close()