Max Jumlah substring unik dari suatu partisi

Saya memodifikasi judulnya agar lebih mudah dimengerti.

Ini adalah versi detail dari pertanyaan:

Kami memiliki string s dan ingin membaginya menjadi substring . Setiap substring berbeda satu sama lain. Berapa jumlah maksimum substring unik yang dapat kita miliki dari satu potongan. Dengan kata lain, berapa jumlah maksimum substring unik yang digabungkan untuk dibentuk s.

Berikut ini beberapa contohnya:

Example 1
s = 'aababaa'
output = 4
Explain: we can split `s` into aa|b|aba|a or aab|a|b|aa, 
         and 4 is the max number of substrings we can get from one split.

Example 2
s = 'aba'
output = 2
Explain: a|ba

Example 3
s = 'aaaaaaa'
output = 3
Explain: a|aa|aaaa

Catatan : shanya berisi karakter huruf kecil. Saya tidak diberi tahu berapa lama sdan karenanya tidak dapat menebak kompleksitas waktu yang optimal. :(

Apakah ini masalah NP-hard? Jika tidak, bagaimana saya bisa menyelesaikannya dengan efisien?

Saya mendengar masalah ini dari salah satu teman saya dan tidak bisa menjawabnya. Saya mencoba menggunakan Trie + serakah untuk menyelesaikan masalah ini. Metode gagal untuk contoh pertama.

Inilah solusi Trie yang saya buat:

def triesolution(s):
    trie = {}
    p = trie
    output = 0
    for char in s:
        if char not in p:
            output += 1
            p[char] = {}
            p = trie
        else:
            p = p[char]
    return output

Misalnya 1, kode di atas akan mengembalikan 3 karena mencoba untuk dipecah smenjadi a|ab|abaa.

Tambahkan: Berkat ide semua orang, sepertinya masalah ini sangat dekat dengan masalah NP. Saat ini, saya mencoba memikirkannya dari arah ini. Misalkan kita memiliki fungsi Guess(n). Fungsi ini akan kembali Truejika kita dapat menemukan nsubstring unik dari satu split atau Falsesebaliknya. Satu pengamatan di sini adalah bahwa jika Guess(n) == True, maka Guess(i) == Trueuntuk semua i <= n. Karena kita dapat menggabungkan dua substring yang berdekatan menjadi satu. Pengamatan ini dapat mengarah pada solusi biner. Namun, itu tetap mengharuskan kita dapat menghitung Guessfungsi dengan sangat efisien. Sayangnya, saya masih tidak dapat menemukan cara polinomial untuk menghitung Guess(n).

Ini dikenal sebagai masalah partisi string yang sadar-tabrakan dan ditunjukkan sebagai NP-lengkap dengan pengurangan dari 3-SAT dalam sebuah makalah oleh Anne Condon, Ján Maňuch dan Chris Thachuk - Kompleksitas masalah partisi string yang sadar-tabrakan dan hubungan dengan desain oligo untuk sintesis gen ( International Computing and Combinatorics Conference , 265-275, 2008).

(Banyak terima kasih kepada Gilad Barkan (גלעד ברקן) karena membuat saya mengetahui diskusi ini.)

Izinkan saya membagikan pemikiran saya tentang masalah ini dari sudut pandang teoretis murni (perhatikan bahwa saya juga menggunakan "faktor" dan bukan "subword").

Saya pikir definisi masalah (atau masalah) yang cukup formal yang dipertimbangkan di sini adalah sebagai berikut:

Diberi kata w, temukan kata u_1, u_2, ..., u_k sedemikian rupa

• u_i! = u_j untuk setiap i, j dengan 1 <= i <j <= k dan
• u_1 u_2 ... u_k = w

Varian maksimisasi (kami ingin banyak u_i): maksimalkan k

Varian minimalisasi (kami ingin u_i pendek): meminimalkan maks {| u_i | : 1 <= i <= k}

Masalah-masalah ini menjadi masalah keputusan dengan tambahan memberikan B terikat, yang, menurut apakah kita berbicara tentang "banyak faktor" -bervariant atau "faktor pendek" -berbagai, adalah batas bawah pada k (kita ingin setidaknya B faktor), atau batas atas pada maks {| u_i | : 1 <= i <= k} (kami ingin faktor panjang paling banyak B), masing-masing. Untuk membicarakan kekerasan NP, kita perlu membicarakan masalah keputusan.

Mari kita gunakan istilah SF untuk "faktor pendek" -bervariasi dan MF untuk "banyak faktor" -bervariasi. Khususnya, dan ini adalah hal yang sangat krusial, masalahnya didefinisikan sedemikian rupa sehingga kita mendapatkan kata di atas beberapa alfabet yang tidak dibatasi dengan cara apa pun. Versi masalahnya adalah kita tahu apriori bahwa kita hanya mendapatkan kata-kata masukan, misalnya, alfabet {a, b, c, d} adalah masalah yang berbeda! Kekerasan NP tidak secara otomatis terbawa dari varian "tidak dibatasi" ke varian "alfabet tetap" (yang terakhir mungkin lebih sederhana).

SF dan MF adalah masalah NP-complete. Ini telah ditunjukkan dalam [1, 1b] dan [2], masing-masing (seperti yang telah ditunjukkan oleh Gilad). Jika saya memahami definisi masalah informal (mungkin juga) di sini di awal diskusi ini dengan benar, maka masalah diskusi ini persis adalah masalah MF. Pada awalnya tidak disebutkan bahwa kata-kata dibatasi untuk berasal dari beberapa alfabet tetap, kemudian dikatakan bahwa kita dapat mengasumsikan bahwa hanya huruf kecil yang digunakan. Jika ini berarti bahwa kita hanya mempertimbangkan kata-kata di atas alfabet tetap {a, b, c, ..., z}, maka ini akan banyak berubah sebenarnya dalam hal kekerasan NP.

Pandangan yang lebih dekat mengungkapkan beberapa perbedaan dalam kompleksitas SF dan MF:

1. kertas [1, 1b] menunjukkan bahwa SF tetap NP-lengkap jika kita memperbaiki alfabet menjadi satu biner (lebih tepatnya: mendapatkan kata w di atas huruf a dan b dan B terikat, dapatkah kita memfaktorkannya dalam faktor-faktor berbeda panjang di kebanyakan B?).
2. kertas [1, 1b] menunjukkan bahwa SF tetap NP-lengkap jika kita memperbaiki batas B = 2 (lebih tepatnya: mendapatkan kata w, bisakah kita memfaktorkannya dalam faktor berbeda panjang paling banyak 2?).
3. kertas [3] menunjukkan bahwa jika alfabet dan B terikat diperbaiki, maka SF dapat diselesaikan dalam waktu polinomial.
4. kertas [2] menunjukkan bahwa MF adalah NP-complete, tetapi hanya jika alfabet tidak dibatasi atau diperbaiki secara apriori! Secara khusus, itu tidak menjawab pertanyaan apakah masalahnya NP-lengkap jika kita hanya mempertimbangkan kata-kata input dari beberapa alfabet tetap (seperti yang biasa terjadi dalam pengaturan praktis).
5. kertas [3] menunjukkan bahwa MF dapat diselesaikan dalam waktu polinomial jika batas input B lagi dibatasi oleh beberapa konstanta, yaitu, input masalah adalah kata dan terikat B dari {1, 2, ..., K} , di mana K adalah konstanta tetap.

Beberapa komentar pada hasil ini: Wrt (1) dan (2), secara intuitif jelas bahwa jika alfabet adalah biner, maka, untuk membuat masalah SF sulit, batas B tidak dapat diperbaiki juga. Sebaliknya, memperbaiki B = 2 berarti bahwa ukuran alfabet harus agak besar untuk menghasilkan instance yang sulit. Akibatnya, (3) agak sepele (pada kenyataannya, [3] mengatakan sedikit lebih: kita dapat menyelesaikannya dalam waktu berjalan tidak hanya polinomial, tetapi juga | w | ^ 2 kali faktor yang hanya tergantung pada ukuran alfabet dan terikat B). (5) tidak sulit juga: Jika kata kita panjang dibandingkan dengan B, maka kita bisa mendapatkan factorisation yang diinginkan dengan hanya mengiris faktor-faktor dengan panjang yang berbeda. Jika tidak, maka kita dapat memaksa semua kemungkinan, yang hanya bersifat eksponensial dalam B, yang dalam hal ini dianggap konstan.

Jadi gambar yang kita miliki adalah sebagai berikut: SF tampaknya lebih sulit, karena kita memiliki kekerasan bahkan untuk huruf tetap atau B. terikat. Masalahnya MF, di sisi lain, mendapat poly-time dipecahkan jika ikatan diperbaiki (dalam hal ini lebih mudah daripada SF), sedangkan pertanyaan yang sesuai dengan ukuran alfabet terbuka. Jadi MF sedikit lebih kompleks daripada SF, bahkan jika ternyata MF untuk huruf tetap juga NP-complete. Namun, jika dapat ditunjukkan bahwa MF dapat diselesaikan untuk huruf tetap dalam waktu-poli, maka MF terbukti jauh lebih mudah daripada SF ... karena satu kasus yang sulitnya agak buatan (alfabet tak terikat!) .

Saya memang berusaha menyelesaikan kasus MF dengan alfabet terbatas, tetapi saya tidak bisa menyelesaikannya dan berhenti mengerjakannya sejak itu. Saya tidak percaya bahwa peneliti lain telah berusaha sangat keras untuk menyelesaikannya (jadi ini bukan salah satu dari masalah yang sangat sulit ini, banyak orang sudah mencoba dan gagal; saya menganggap itu bisa dilakukan). Dugaan saya adalah bahwa ini juga NP-hard untuk huruf tetap, tetapi mungkin pengurangannya sangat rumit sehingga Anda akan mendapatkan sesuatu seperti "MF sulit untuk huruf ukuran 35 atau lebih besar" atau sesuatu, yang tidak akan super bagus juga .

Mengenai literatur lebih lanjut, saya tahu makalah [4], yang mempertimbangkan masalah pemisahan kata w menjadi faktor berbeda u_1, u_2, ..., u_k yang semuanya palindrom, yang juga NP-complete.

Saya melihat sekilas kertas [5], ditunjukkan oleh Gilad. Tampaknya mempertimbangkan pengaturan yang berbeda. Dalam makalah ini, penulis tertarik pada pertanyaan kombinatorial tentang berapa banyak kata atau subword yang berbeda dapat terkandung dalam kata yang diberikan, tetapi ini dapat tumpang tindih. Misalnya, aaabaab berisi 20 subword berbeda a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (mungkin saya salah hitung, tetapi Anda mendapatkan idenya). Beberapa dari mereka hanya memiliki satu kejadian, seperti baa, beberapa dari mereka beberapa, seperti aa. Bagaimanapun, pertanyaannya bukanlah bagaimana kita dapat memisahkan kata tersebut untuk mendapatkan banyak faktor berbeda, karena ini berarti setiap simbol individu berkontribusi tepat pada satu faktor.

Mengenai solusi praktis untuk masalah seperti ini (perlu diingat bahwa saya adalah ahli teori, jadi ambil ini dengan sebutir garam):

• Setahu saya, tidak ada batas teoritis yang lebih rendah (seperti NP-hardness) yang akan mengesampingkannya untuk menyelesaikan MF dalam waktu polinomial jika kita hanya mempertimbangkan memasukkan kata-kata di atas alfabet tetap. Namun ada satu peringatan: Jika Anda mendapatkan algoritma poli-waktu, maka ini harus berjalan secara eksponensial dalam jumlah simbol dari alfabet tetap (atau eksponensial pada beberapa fungsi itu)! Kalau tidak, itu juga akan menjadi algoritma waktu polinomial untuk kasus huruf yang tidak terikat. Jadi, sebagai ahli teori, saya akan mencari tugas algoritmik yang dapat dihitung dalam waktu eksponensial hanya jika jumlah simbol dan yang entah bagaimana membantu merancang algoritma untuk MF. Di sisi lain, ada kemungkinan bahwa algoritma seperti itu tidak ada dan MF juga NP-hard dalam kasus alfabet tetap.

• Jika Anda tertarik pada solusi praktis, mungkin ada baiknya untuk memperkirakan solusinya. Jadi mendapatkan factorisation yang dijamin hanya setengah dari yang optimal dalam kasus terburuk tidak akan terlalu buruk.

• Heuristik yang tidak memberikan rasio perkiraan yang dapat dibuktikan, tetapi bekerja dengan baik dalam pengaturan praktis juga akan menarik, saya kira.

• Mengubah instance instans menjadi SAT atau ILP-instance seharusnya tidak terlalu sulit dan kemudian Anda bisa menjalankan SAT atau ILP-Solver untuk mendapatkan solusi yang optimal.

• Pendapat pribadi saya adalah bahwa meskipun tidak diketahui apakah huruf tetap-MF adalah NP-keras, ada cukup wawasan teoritis yang menunjukkan bahwa masalahnya cukup sulit sehingga dibenarkan untuk mencari solusi heuristik dll. bekerja dengan baik dalam lingkungan yang praktis.

Bibliografi:

[1] Anne Condon, Ján Manuch, Chris Thachuk: Kompleksitas partisi string. J. Discrete Algorithms 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Kompleksitas Masalah Partisi Tali Tabrakan-Sadar dan Hubungannya dengan Desain Oligo untuk Sintesis Gen. COCOON 2008: 265-275

[2] Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid: Pencocokan Pola dengan Variabel: Algoritma Cepat dan Hasil Kekerasan Baru. STACS 2015: 302-315

[3] Markus L. Schmid: Menghitung faktorisasi string yang bebas kesetaraan dan berulang. Teor Komputasi. Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: Beragam Faktor Palindromik NP-Lengkap. Int. J. Ditemukan. Komputasi. Sci. 29 (2): 143-164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: String dengan Sub maksimalences dan Substring yang Berbeda. Electr. J. Comb. 11 (1) (2004)

Inilah solusi tetapi ia meledak dengan sangat cepat dan tidak berada di dekat solusi yang efisien. Pertama-tama memecah string menjadi daftar substring unik tanpa memperhatikan urutan, kemudian mencoba untuk menggunakan itertools.permutation untuk merakit kembali substring-substring tersebut kembali ke string asli, menguji permutasi SETIAP untuk melihat apakah cocok dengan string asli.

import itertools as it

def splitter(seq):                                                             
    temp = [seq]
    for x in range(1, len(seq)):
        print(seq[:x], seq[x:])
        temp.append(seq[:x])
        temp.append(seq[x:])
    return temp

if __name__ == "__main__":
    test = input("Enter a string: ")
    temp = splitter(test)
    copy = temp[::]
    condition = True
    for x in temp:
        if len(x) > 1:
            copy.extend(splitter(x))
    copy = sorted(list(set(copy)))
    print(copy)
    count = []
    for x in range(len(test)):
        item = it.permutations(copy, x)
        try:
            while True:
                temp = next(item)
                if "".join(list(temp)) == test:
                    if len(temp) == len(set(temp)):
                        count.append((len(temp), temp))
        except StopIteration:
            print('next permutation begin iteration')
            continue
    print(f"All unique splits: {count}")
    print(f"Longest unique split : {max(count)[0]}")

Untuk tes pertama kita mendapatkan ini:

All unique splits: [(1, ('aababaa',)), (2, ('a', 'ababaa')), (2, ('aa', 'babaa')), (2, 
('aab', 'abaa')), (2, ('aaba', 'baa')), (2, ('aabab', 'aa')), (2, ('aababa', 'a')), (3, 
('a', 'ab', 'abaa')), (3, ('a', 'aba', 'baa')), (3, ('a', 'abab', 'aa')), (3, ('aa', 'b',
 'abaa')), (3, ('aa', 'ba', 'baa')), (3, ('aa', 'baba', 'a')), (3, ('aab', 'a', 'baa')),
 (3, ('aab', 'ab', 'aa')), (3, ('aab', 'aba', 'a')), (3, ('aaba', 'b', 'aa')), (3,
 ('aaba', 'ba', 'a')), (4, ('a', 'aba', 'b', 'aa')), (4, ('aa', 'b', 'a', 'baa')), (4,
 ('aa', 'b', 'aba', 'a')), (4, ('aab', 'a', 'b', 'aa'))]
Longest unique split : 4

Mungkin ini bisa dioptimalkan entah bagaimana, tetapi itu membutuhkan beberapa detik pada mesin ini.

Saya telah mencoba masalah ini dan memikirkannya dalam hal atau apakah akan membuat partisi pada indeks yang diberikan. Jadi fungsi ini bersifat rekursif dan membuat 2 cabang di setiap indeks 1. Jangan partisi di indeks i 2. Partisi di indeks i.

Berdasarkan partisi saya mengisi satu set dan kemudian mengembalikan ukuran set

def max(a,b):
    if a>b: return a
    return b



def keep(last, current, inp, map):
    # print last
    # print current
    # print map

    if len(inp) == 2 :
        if inp[0]==inp[1]: return 1
        return 2

    if current >= len(inp):
        return len(map)
    // This is when we are at the start of the string. 
    // In this case we can only do one thing not partition and thus take the entire string as a possible string.

    if current == last :
        map11 = map.copy()
        map11.add(inp[current:])
        return keep(last, current + 1, inp, map11)

    map1 = map.copy();
    if current != (len(inp)-1):
        map1.add(inp[last:current])

    map2 = map.copy()

    return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1))

print keep(0,0,"121", set([]))
print keep(0,0,"aaaaaaa", set([]))
print keep(0,0,"aba", set([]))
print keep(0,0,"aababaa", set([]))
print keep(0,0,"21", set([]))
print keep(0,0,"22", set([]))

https://onlinegdb.com/HJynWw-iH

Anda dapat menggunakan fungsi rekursif dengan set sebagai parameter kedua untuk melacak string unik di jalur saat ini sejauh ini. Untuk setiap rekursi, ulangi semua indeks ditambah 1 untuk membagi string untuk string kandidat yang mungkin, dan jika string kandidat belum diatur, buat panggilan rekursif dengan string yang tersisa dan kandidat ditambahkan ke set. untuk mendapatkan jumlah maksimum substring unik dari string yang tersisa, tambahkan 1 padanya dan kembalikan maksimum maksimum dari iterasi. Kembalikan 0 jika string yang diberikan kosong atau semua string kandidat sudah ada di set:

def max_unique_substrings(s, seen=()):
    maximum = 0
    for i in range(1, len(s) + 1):
        candidate = s[:i]
        if candidate not in seen:
            maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen}))
    return maximum

Demo: https://repl.it/@blhsing/PriceyScalySphere

Dalam Python 3.8, logika di atas juga dapat ditulis dengan panggilan ke maxfungsi dengan ekspresi generator yang menyaring kandidat yang telah "dilihat" dengan ekspresi tugas:

def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

Berikut ini adalah jawaban berdasarkan teori grafik.

Pemodelan
Masalah ini dapat dimodelkan sebagai masalah set independen maksimum pada grafik ukuran O(n²)sebagai berikut:
Membiarkan w = c_1, ..., c_nmenjadi string input.
Membiarkan G = (V,E)menjadi sebuah grafik diarahkan, dibangun sebagai berikut:
V = { (a, b) such that a,b in [1, n], a <= b }. Kita dapat melihat bahwa ukurannya Vadalah n(n-1)/2, di mana setiap simpul mewakili substring w.
Kemudian, untuk setiap pasangan simpul (a1, b1)dan (a2, b2), kami membangun tepi ((a1, b1), (a2, b2))iff
(i) [a1, b1]berpotongan [a2, b2]atau
(ii) c_a1...c_b1 = c_a2...c_b2.
Mengatakan sebaliknya, kami membangun tepi antara dua simpul jika (i) substring yang mereka tumpang tindih watau (ii) dua substring sama.

Kami kemudian bisa melihat mengapa set independen maksimal dari Gmenyediakan jawaban untuk masalah kita.

Kompleksitas
Dalam kasus umum, masalah set independen maksimum (MIS) adalah NP-hard, dengan kompleksitas waktu O(1.1996^n)dan dalam ruang polinomial [Xiao, NamaGoshi (2017)] .
Pada awalnya saya berpikir bahwa grafik yang dihasilkan akan menjadi grafik chordal (tidak ada siklus panjang> 3), yang akan sangat bagus sejak saat itu masalah MIS dapat diselesaikan dalam waktu linier pada kelas grafik ini.
Tapi saya segera menyadari bahwa itu tidak terjadi, cukup mudah untuk menemukan contoh di mana ada siklus panjang 5 dan lebih banyak.
Sebenarnya, grafik yang dihasilkan tidak menunjukkan properti 'bagus' yang biasanya kita cari dan yang memungkinkan untuk mengurangi kompleksitas masalah MIS menjadi polinomial.
Ini hanya batas atas pada kompleksitas masalah, karena pengurangan waktu polinomial hanya berjalan dalam satu arah (kita dapat mengurangi masalah ini menjadi masalah MIS, tetapi tidak sebaliknya, setidaknya tidak sepele). Jadi pada akhirnya kami akhirnya memecahkan masalah ini dalam O(1.1996^(n(n-1)/2))kasus terburuk.
Jadi, sayangnya, saya tidak bisa membuktikan bahwa itu dalam P, atau bahwa itu NP-lengkap atau NP-keras. Satu hal yang pasti adalah bahwa masalahnya ada di NP, tapi saya kira ini bukan kejutan bagi siapa pun.

Implementasi
Keuntungan mengurangi masalah ini menjadi masalah SIM adalah SIM adalah masalah klasik, di mana beberapa implementasi dapat ditemukan, dan bahwa masalah SIM juga mudah ditulis sebagai ILP.
Berikut adalah formulasi ILP dari masalah SIM:

Objective function 
maximize sum(X[i], i in 1..n)
Constraints:
for all i in 1..n, X[i] in {0, 1}
for all edge (i, j), X[i] + X[j] <= 1

Menurut pendapat saya, itu harus menjadi cara yang paling efisien untuk menyelesaikan masalah ini (menggunakan pemodelan ini sebagai masalah SIM), karena pemecah ILP sangat efisien, terutama ketika menyangkut masalah besar.

Ini adalah implementasi yang saya lakukan menggunakan Python3 dan GLPK solver. Untuk mengujinya, Anda memerlukan pemecah LP yang kompatibel dengan format file Cplex.

from itertools import combinations

def edges_from_string(w):
    # build vertices
    vertices = set((a, b) for b in range(len(w)) for a in range(b+1))
    # build edges
    edges = {(a, b): set() for (a, b) in vertices}
    for (a1, b1), (a2, b2) in combinations(edges, 2):
        # case: substrings overlap
        if a1 <= a2 <= b1:
            edges[(a1, b1)].add((a2, b2))
        if a2 <= a1 <= b2:
            edges[(a2, b2)].add((a1, b1))
        # case: equal substrings
        if w[a1:b1+1] == w[a2:b2+1]:
            if a1 < a2:
                edges[(a1, b1)].add((a2, b2))
            else:
                edges[(a2, b2)].add((a1, b1))
    return edges

def write_LP_from_edges(edges, filename):
    with open(filename, 'w') as LP_file:
        LP_file.write('Maximize Z: ')
        LP_file.write("\n".join([
            "+X%s_%s" % (a, b)
            for (a, b) in edges
        ]) + '\n')
        LP_file.write('\nsubject to \n')
        for (a1, b1) in edges:
            for (a2, b2) in edges[(a1, b1)]:
                LP_file.write(
                    "+X%s_%s + X%s_%s <= 1\n" %
                    (a1, b1, a2, b2)
                )
        LP_file.write('\nbinary\n')
        LP_file.write("\n".join([
            "X%s_%s" % (a, b)
            for (a, b) in edges.keys()
        ]))
        LP_file.write('\nend\n')
write_LP_from_edges(edges_from_string('aababaa'), 'LP_file_1')
write_LP_from_edges(edges_from_string('kzshidfiouzh'), 'LP_file_2')

Anda kemudian dapat menyelesaikannya dengan glpsolperintah:
glpsol --lp LP_file_1
Yang aababaadiselesaikan dengan cepat (0,02 detik pada laptop saya), tetapi seperti yang diharapkan, banyak hal menjadi (lebih banyak) lebih keras ketika ukuran string tumbuh ....
Program ini hanya memberikan nilai numerik (dan tidak partisi optimal), namun demikian partisi optimal dan substring yang sesuai dapat ditemukan dengan implementasi yang serupa, menggunakan antarmuka LP solver / python seperti pyomo

Waktu & memori
aababaa : 0,02 detik, 0,4 MB, nilai: 4
kzshidfiouzh: 1,4 detik, 3,8 MB, nilai: 10
aababababbababab: 60,2 detik, 31,5 MB, nilai: 8
kzshidfiouzhsdjfyu: 207,5 detik, 55,7 MB, nilai: 14
Perhatikan bahwa pemecah LP juga menawarkan batas bawah dan atas saat ini pada solusi, jadi untuk contoh terakhir, saya bisa mendapatkan solusi yang sebenarnya sebagai batas bawah setelah satu menit.

Jawaban saya yang lain terkait erat tetapi tidak sesuai persis dengan masalah ini, meninggalkan ambigu apakah menemukan factorisation string bebas kesetaraan terbesar mungkin dari kelas kompleksitas yang berbeda dari apakah ada factorisation bebas kesetaraan dengan panjang faktor terikat (yang terakhir ditangani oleh kertas yang dikutip).

Dalam makalah, Pencocokan pola dengan variabel: Algoritme cepat dan hasil kekerasan baru (Henning Fernau, Florin Manea, Robert Mercaş, dan Markus L. Schmid, dalam Proc. Simposium ke-32 tentang Aspek Teoretis Ilmu Komputer, STACS 2015, volume 30 dari Leibniz Prosiding Internasional dalam Informatika (LIPIcs) , halaman 302–315, 2015), penulis menunjukkan bahwa NP-complete untuk memutuskan, untuk angka kdan kata tertentu w, apakah wdapat difaktorkan menjadi kfaktor yang berbeda.

Jika kita mempertimbangkan komentar templatetypedef , menyiratkan mungkin ada solusi waktu polinomial untuk factorisation bebas kesetaraan terbesar yang tidak dibatasi maka pasti kita dapat menggunakan algoritma semacam itu untuk menjawab jika kita dapat membagi string menjadi kfaktor yang berbeda (substring) dengan hanya mengamati apakah kada kurang dari maks yang sudah kita tahu.

Schmid (2016), bagaimanapun, menulis bahwa "masih merupakan masalah terbuka apakah MaxEFF-s tetap NP-complete jika alfabetnya diperbaiki." (Menghitung faktorisasi string yang bebas kesetaraan dan berulang, Ilmu Komputer Teoritis Volume 618 , 7 Maret 2016, Halaman 42-51)

Ukuran Factorisation Bebas Maximum Maksimum (MaxEFF-s) masih parameter, dan didefinisikan sebagai:

Misalnya: Sebuah kata wdan angka m, 1 ≤ m ≤ |w|.

Pertanyaan: Apakah terdapat sebuah factorisation p kesetaraan bebas wdengan s(p) ≥ m? ( s(p)Menjadi ukuran factorisation.)