Menemukan kecocokan semua-kecuali-satu

18

Tantangan ini adalah tentang menulis kode untuk menyelesaikan masalah berikut.

Diberikan dua string A dan B, kode Anda harus menampilkan awal dan akhir indeks substring A dengan properti berikut.

  • Substring A juga harus cocok dengan beberapa substring B dengan hingga satu subtitusi karakter tunggal dalam string.
  • Seharusnya tidak ada lagi substring A yang memenuhi properti pertama.

Sebagai contoh:

A = xxxappleyyyyyyy

B = zapllezzz

Substring appledengan indeks 4 8(pengindeksan dari 1) akan menjadi output yang valid.

Skor

Skor jawaban Anda akan menjadi jumlah panjang kode Anda dalam byte + waktu dalam detik di komputer saya saat dijalankan dengan string A dan B dengan panjang masing-masing 1 juta.

Pengujian dan input

Saya akan menjalankan kode Anda pada dua string dengan panjang 1 juta yang diambil dari string di http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/

Input akan pada standar masuk dan hanya akan menjadi dua string, dipisahkan oleh baris baru.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga open source dan tersedia secara bebas untuk Linux.

Mesin saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai konsekuensinya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.

isaacg
sumber
Anda membutuhkan lebih banyak definisi skor absolut. Menjalankan waktu di komputer Anda tidak terdengar seperti metode penilaian yang baik.
mbomb007
7
@ mbomb007 Ini satu-satunya cara yang masuk akal untuk mengukur kecepatan kode dan merupakan yang selalu digunakan dalam kompetisi kode tercepat di PPCG! Orang-orang biasanya memposting skor mereka di komputer mereka sendiri dalam jawaban mereka dan menunggu OP untuk kemudian menghasilkan skor yang pasti. Setidaknya 100% tidak ambigu.
5
@ mbomb007 yang merupakan metode penilaian yang sangat banyak digunakan untuk kode tercepat.
Pengoptimal
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..-- pikiran?
John Dvorak
2
@FryAmTheEggman Dalam acara yang sangat tidak mungkin seri, jawaban pertama menang. appleyperlu dua pergantian pemain untuk mencocokkan apllez. Mungkin Anda melewatkannya aplldi B dan bukan appl?

Jawaban:

4

Waktu C ++: O (n ^ 2), ruang ekstra: O (1)

Dibutuhkan 0.2s untuk menyelesaikan data 15K pada mesin saya.

Untuk mengkompilasinya, gunakan:

g++ -std=c++11 -O3 code.cpp -o code

Untuk menjalankannya, gunakan:

./code < INPUT_FILE_THAT_CONTAINS_TWO_LINES_SPERATED_BY_A_LINE_BREAK

Penjelasan

Idenya sederhana, untuk string s1dan s2, kami mencoba mengimbangi s2dengan i:

s1: abcabcabc
s2: bcabcab

Saat offset 3:

s1: abcabcabc
s2:    bcabcab

Kemudian, untuk setiap offset i, kami melakukan pemindaian program dinamis pada s1[i:]dan s2. Untuk masing-masing j, biarkan f[j, 0]menjadi panjang maksimum dsedemikian rupa s1[j - d:j] == s2[j - i - d: j - i]. Demikian pula, mari f[j, 1]menjadi panjang maksimum dsedemikian sehingga string s1[j - d:j]dan s2[j - i - d:j - i]berbeda paling banyak 1 karakter.

Jadi untuk s1[j] == s2[j - i], kami memiliki:

f[j, 0] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j]
f[j, 1] = f[j - 1, 1] + 1  // concat solution in f[j - 1, 1] and s1[j]

Jika tidak:

f[j, 0] = 0  // the only choice is empty string
f[j, 1] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j] (or s2[j - i])

Dan:

f[-1, 0] = f[-1, 1] = 0 

Karena kita hanya perlu f [j - 1,:] untuk menghitung f [j,:], hanya O (1) ruang ekstra yang digunakan.

Akhirnya, panjang maks adalah:

max(f[j, 1] for all valid j and all i)

Kode

#include <string>
#include <cassert>
#include <iostream>

using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n1, n2;
    n1 = s1.size();
    n2 = s2.size();
    int max_len = 0;
    int max_end = -1;
    for(int i = 1 - n2; i < n1; i++) {
        int f0, f1;
        int max_len2 = 0;
        int max_end2 = -1;
        f0 = f1 = 0;
        for(int j = max(i, 0), j_end = min(n1, i + n2); j < j_end; j++) {
            if(s1[j] == s2[j - i]) {
                f0 += 1;
                f1 += 1;
            } else {
                f1 = f0 + 1;
                f0 = 0;
            }
            if(f1 > max_len2) {
                max_len2 = f1;
                max_end2 = j + 1;
            }
        }
        if(max_len2 > max_len) {
            max_len = max_len2;
            max_end = max_end2;
        }
    }
    assert(max_end != -1);
    // cout << max_len << endl;
    cout << max_end - max_len + 1 << " " << max_end << endl;
}
sinar
sumber
Maaf, saya telah melihat kode dan saya tidak dapat menemukan bagaimana memperhitungkan kemungkinan pencocokan string kecuali untuk satu karakter, seperti dalam contoh "apel" dan "aplle". Bisakah Anda jelaskan?
rorlork
@ rcrmn Itulah yang dilakukan bagian pemrograman dinamis. Untuk memahami, sebaiknya coba hitung f [j, 0] dan f [j, 1] secara manual untuk beberapa kasus sederhana. Kode sebelumnya memiliki beberapa bug jadi saya memperbarui posting.
Ray
Terima kasih untuk ini. Apakah Anda pikir mungkin ada solusi O (n log n) juga?
2

C ++

Saya mencoba memikirkan algoritma yang baik untuk melakukan ini, tapi saya agak terganggu hari ini dan tidak bisa memikirkan apa pun yang akan bekerja dengan baik. Ini berjalan pada waktu O (n ^ 3), jadi lambat sekali. Pilihan lain yang saya pikirkan bisa saja secara teori lebih cepat tetapi akan mengambil ruang O (n ^ 2), dan dengan input 1M, bahkan akan lebih buruk.

Memalukan, butuh 190 detik untuk input 15K. Saya akan mencoba memperbaikinya. Sunting: Menambahkan multiprocessing. Sekarang butuh 37 detik untuk input 15K pada 8 utas.

#include <string>
#include <vector>
#include <sstream>
#include <chrono>
#include <thread>
#include <atomic>
#undef cin
#undef cout
#include <iostream>

using namespace std;

typedef pair<int, int> range;

int main(int argc, char ** argv)
{
    string a = "xxxappleyyyyyyy";
    string b = "zapllezzz";

    getline(cin, a);
    getline(cin, b);

    range longestA;
    range longestB;

    using namespace std::chrono;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    unsigned cores = thread::hardware_concurrency(); cores = cores > 0 ? cores : 1;

    cout << "Processing on " << cores << " cores." << endl;

    atomic<int> processedCount(0);

    vector<thread> threads;

    range* longestAs = new range[cores];
    range* longestBs = new range[cores];
    for (int t = 0; t < cores; ++t)
    {
        threads.push_back(thread([&processedCount, cores, t, &a, &b, &longestBs, &longestAs]()
        {
            int la = a.length();
            int l = la / cores + (t==cores-1? la % cores : 0);
            int lb = b.length();
            int aS = t*(la/cores);

            for (int i = aS; i < aS + l; ++i)
            {
                int count = processedCount.fetch_add(1);
                if ((count+1) * 100 / la > count * 100 / la)
                {
                    cout << (count+1) * 100 / la << "%" << endl;
                }
                for (int j = 0; j < lb; ++j)
                {
                    range currentB = make_pair(j, j);
                    bool letterChanged = false;
                    for (int k = 0; k + j < lb && k + i < la; ++k)
                    {
                        if (a[i + k] == b[j + k])
                        {
                            currentB = make_pair(j, j + k);
                        }
                        else if (!letterChanged)
                        {
                            letterChanged = true;
                            currentB = make_pair(j, j + k);
                        }
                        else
                        {
                            break;
                        }
                    }
                    if (currentB.second - currentB.first > longestBs[t].second - longestBs[t].first)
                    {
                        longestBs[t] = currentB;
                        longestAs[t] = make_pair(i, i + currentB.second - currentB.first);
                    }
                }
            }
        }));
    }

    longestA = make_pair(0,0);
    for(int t = 0; t < cores; ++t)
    {
        threads[t].join();

        if (longestAs[t].second - longestAs[t].first > longestA.second - longestA.first)
        {
            longestA = longestAs[t];
            longestB = longestBs[t];
        }
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);

    cout << "First substring at range (" << longestA.first << ", " << longestA.second << "):" << endl;
    cout << a.substr(longestA.first, longestA.second - longestA.first + 1) << endl;
    cout << "Second substring at range (" << longestB.first << ", " << longestB.second << "):" << endl;
    cout << b.substr(longestB.first, longestB.second - longestB.first + 1) << endl;
    cout << "It took me " << time_span.count() << " seconds for input lengths " << a.length() << " and " << b.length() <<"." << endl;

    char c;
    cin >> c;
    return 0;
}
rorlork
sumber
Saya benar-benar minta maaf itu solusi yang buruk. Saya telah mencari sebuah algoritma untuk mencapai ini di waktu yang lebih baik, tetapi tidak menemukan apa pun untuk saat ini ...
rorlork
Nah, kompleksitas tugas yang diperlukan harus sekitar O (n ^ 4) hingga O (n ^ 5), jadi jangka waktu yang lama diberikan
hoffmale
Saya percaya itu harus lebih seperti O (n ^ 3) pada kasus terburuk, paling tidak dengan algoritma saya itu. Bagaimanapun, saya yakin sesuatu dapat dilakukan untuk memperbaikinya, seperti semacam pencarian pohon, tetapi saya tidak yakin bagaimana itu akan dilaksanakan.
rorlork
Oh ya, O (n ^ 3) itu ... memiliki pendekatan yang berbeda dalam pikiran yang akan mengambil O (n ^ 4), tetapi yang agak tidak berguna sekarang xD
hoffmale
Anda dapat menghemat sedikit waktu jika Anda mengubah tanda centang pada dua terluar untuk loop dari i < a.length()menjadi i < a.length - (longestA.second - longestA.first)(sama untuk j dan b.length ()) karena Anda tidak perlu memproses kecocokan yang lebih kecil dari yang terpanjang saat ini
hoffmale
2

R

Sepertinya saya terlalu memperumit masalah dengan solusi sebelumnya. Ini sekitar 50% lebih cepat (23 detik pada string 15k) dari yang sebelumnya dan cukup sederhana.

rm(list=ls(all=TRUE))
a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
matchLen=1
matchIndex=1
indexA = 1
repeat {    
    i = 0
    repeat {
        srch = substring(a,indexA,indexA+matchLen+i)
        if (agrepl(srch,b,max.distance=list(insertions=0,deletions=0,substitutions=1)))
            i = i + 1
        else {
            if (i > 0) {
                matchLen = matchLen + i - 1
                matchIndex = indexA
            }
            break
        }
    }
    indexA=indexA+1
    if (indexA + matchLen > nchar(a)) break
}
c(matchIndex, matchLen + matchIndex)
print (substring(a,matchIndex, matchLen + matchIndex))
print(proc.time()-s)

Ini tidak akan pernah menjadi pesaing karena bahasa, tetapi saya memang bersenang-senang melakukannya.
Tidak yakin dengan kerumitannya, tetapi lebih dari beberapa string ~ 15k dibutuhkan 43 detik menggunakan utas tunggal. Bagian terbesar dari itu adalah penyortiran array. Saya mencoba beberapa perpustakaan lain, tetapi tanpa perbaikan yang signifikan.

a="xxxappleyyyyyyy"
b="zapllezzz"
s=proc.time()
N=nchar
S=substring
U=unlist
V=strsplit
A=N(a)
B=N(b)
a=S(a,1:A)
b=S(b,1:B)
a=sort(a,method="quick")
b=sort(b,method="quick")
print(proc.time()-s)
C=D=1
E=X=Y=I=0
repeat{
    if(N(a[C])>E && N(b[D])>E){
        for(i in E:min(N(a[C]),N(b[D]))){
            if (sum(U(V(S(a[C],1,i),''))==U(V(S(b[D],1,i),'')))>i-2){
                F=i
            } else break
        }
        if (F>E) {
            X=A-N(a[C])+1
            Y=X+F-1
            E=F
        }
        if (a[C]<b[D])
            C=C+1
            else
            D=D+1
    } else
        if(S(a[C],1,1)<S(b[D],1,1))C=C+1 else D=D+1
    if(C>A||D>B)break
}
c(X,Y)
print(proc.time()-s)

Metode:

  • Buat array suffix untuk setiap string
  • Pesan susunan sufiks
  • Langkah melalui masing-masing array dalam semacam cara membandingkan awal masing-masing
MickyT
sumber
Tentu saja, solusi termudah dalam R adalah menggunakan Bioconductor.
archaephyrryx
@archaephyrryx Solusi biokonduktor akan menyenangkan.
Mungkin ... Tapi membaca cepat saya tentang dokumen itu jauh di atas kepala saya. Mungkin jika saya mengerti ketentuannya :-)
MickyT
Saya menghapus komentar pertama saya. Tentu saja Anda dapat menggunakan pustaka sumber terbuka apa pun yang Anda suka untuk tantangan ini.