Editing 2929 - Origami (section)

= Exemplu 2: =
<code>origamiIN.txt</code>
 5 4
 baabbaa
 cbbccbb
 ababbab
 cabccba
 bccaacc
<code>origamiOUT.txt</code>
 Datele nu corespund restrictiilor impuse
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(N, M):
    if not (1 <= N <= M and N * M <= 1_000_000 and M <= 600):
        with open("origamiOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def solve(t, N, M, A):
    L = [float('inf')] * (M + 1)
    R = [float('inf')] * (M + 1)
    C = [''] * (2 * M + 1)
    d = [0] * (2 * M + 1)
    pref = [False] * (M + 1)
    suf = [False] * (M + 1)
    
    for i in range(1, N + 1):
        C[0] = '#'
        le, ri, len_ = 0, 0, 0
        for j in range(1, M + 1):
            C[2 * j - 1] = A[t][i][j]
            C[2 * j] = '#'
        size = 2 * M
        d[0] = 0
        for j in range(1, size + 1):
            if j > ri:
                len_ = 0
            else:
                len_ = min(ri - j, d[le + ri - j])
            while j + len_ <= size and j - len_ >= 0 and C[j + len_] == C[j - len_]:
                len_ += 1
            len_ -= 1
            d[j] = len_
            if j + len_ > ri:
                ri = j + len_
                le = j - len_
        for j in range(1, M + 1):
            R[j] = min(R[j], d[2 * j] // 2)
        for j in range(1, M + 1):
            L[j] = R[j - 1]

    pref[M] = True
    suf[1] = True
    last = 1
    for i in range(2, M + 1):
        if L[i] > 0:
            if i - L[i] <= last:
                suf[i] = True
                last = i

    last = M
    for i in range(M, 0, -1):
        if R[i] > 0:
            if i + R[i] >= last:
                pref[i] = True
                last = i

    ret = 0
    cnt = 0
    for i in range(1, M + 1):
        if suf[i]:
            cnt += 1
        if pref[i]:
            ret += cnt
    return ret

def main():
    with open("origamiIN.txt", "r") as fin:
        N, M = map(int, fin.readline().split())
        
        if not verifica_restrictii(N, M):
            return
        
        A = [[None] * (N + 1), [None] * (M + 1)]
        
        for i in range(1, N + 1):
            A[0][i] = ['#'] + list(fin.readline().strip())
        
        for j in range(1, M + 1):
            A[1][j] = ['#'] + [A[0][i][j] for i in range(1, N + 1)]

    with open("origamiOUT.txt", "w") as fout:
        fout.write(str(solve(0, N, M, A) * solve(1, M, N, A)) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==
Este exemplul din desenul de mai sus. Singurele răspunsuri posibile sunt matricea inițială, respectiv submatricea de după aplicarea operației evidențiate în figură.