Encontrar todos los partidos menos uno

18

Este desafío se trata de escribir código para resolver el siguiente problema.

Dadas dos cadenas A y B, su código debería generar los índices de inicio y finalización de una subcadena de A con las siguientes propiedades.

  • La subcadena de A también debe coincidir con alguna subcadena de B con hasta una sustitución de un solo carácter en la cadena.
  • Ya no debería haber una subcadena de A que satisfaga la primera propiedad.

Por ejemplo:

A = xxxappleyyyyyyy

B = zapllezzz

La subcadena applecon índices 4 8(indexación desde 1) sería una salida válida.

Puntuación

El puntaje de su respuesta será la suma de la longitud de su código en bytes + el tiempo en segundos que le toma a mi computadora cuando se ejecuta en las cadenas A y B de 1 millón de longitud cada una.

Prueba y entrada

Ejecutaré su código en dos cadenas de longitud 1 millón tomadas de las cadenas en http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/

La entrada estará en entrada estándar y será simplemente dos cadenas, separadas por una nueva línea.

Idiomas y bibliotecas

Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux y cualquier biblioteca que también sea de código abierto y esté disponible gratuitamente para Linux.

Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de ubuntu en un procesador AMD FX-8350 de ocho núcleos. Esto también significa que necesito poder ejecutar su código. Como consecuencia, solo use software gratuito fácilmente disponible e incluya instrucciones completas sobre cómo compilar y ejecutar su código.

isaacg
fuente
Necesita una definición de puntuación más absoluta. El tiempo de ejecución en su computadora no parece un buen método de puntuación.
mbomb007
77
@ mbomb007 ¡Es la única forma sensata de medir la velocidad del código y es la que siempre se usa en las competencias de código más rápidas en PPCG! La gente normalmente publica su puntaje en su propia computadora en su respuesta y espera a que el OP produzca un puntaje definitivo. Es 100% inequívoco al menos.
55
@ mbomb007 que es un método de puntuación muy utilizado para el código más rápido.
Optimizador
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..- pensamientos?
John Dvorak
2
@FryAmTheEggman En el caso muy improbable de un empate, la primera respuesta gana. appleynecesita dos sustituciones para que coincida apllez. ¿Tal vez te perdiste que está apllen B y no appl?

Respuestas:

4

Tiempo C ++: O (n ^ 2), espacio extra: O (1)

Se necesitan 0.2s para completar los datos de 15K en mi máquina.

Para compilarlo, use:

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

Para ejecutarlo, use:

./code < INPUT_FILE_THAT_CONTAINS_TWO_LINES_SPERATED_BY_A_LINE_BREAK

Explicación

La idea es simple, para string s1y s2, tratamos de compensarlo s2por i:

s1: abcabcabc
s2: bcabcab

Cuando el desplazamiento es 3:

s1: abcabcabc
s2:    bcabcab

Luego, para cada desplazamiento i, realizamos una exploración de programación dinámica en s1[i:]y s2. Para cada uno j, f[j, 0]sea ​​la longitud máxima dtal que s1[j - d:j] == s2[j - i - d: j - i]. Del mismo modo, deje f[j, 1]que la longitud máxima sea dtal que las cadenas s1[j - d:j]y s2[j - i - d:j - i]difieran en a lo sumo 1 carácter.

Entonces s1[j] == s2[j - i], tenemos:

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]

De otra manera:

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])

Y:

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

Como solo necesitamos f [j - 1,:] para calcular f [j,:], solo se utiliza O (1) espacio extra.

Finalmente, la longitud máxima será:

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

Código

#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;
}
Rayo
fuente
Lo siento, he estado mirando el código y no puedo encontrar cómo tiene en cuenta la posibilidad de que las cadenas coincidan, excepto por un carácter, como en el ejemplo "manzana" y "aplle". ¿Podrías explicar?
rorlork
@rcrmn Eso es lo que hace la parte de programación dinámica. Para entenderlo, es útil intentar calcular f [j, 0] yf [j, 1] manualmente para algunos casos simples. El código anterior tiene algunos errores, así que actualicé la publicación.
Ray
Gracias por esto. ¿Crees que también podría haber una solución O (n log n)?
2

C ++

Traté de pensar en un buen algoritmo para hacer esto, pero hoy estoy un poco distraído y no se me ocurre nada que funcione bien. Esto se ejecuta en el tiempo O (n ^ 3), por lo que es muuuy lento. La otra opción en la que pensé podría haber sido teóricamente más rápida, pero habría ocupado el espacio O (n ^ 2), y con entradas de 1M, incluso hubiera sido peor.

Es vergonzoso, toma 190 segundos para entradas de 15K. Intentaré mejorarlo. Editar: Se agregó multiprocesamiento. Ahora toma 37 segundos para una entrada de 15K en 8 hilos.

#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
fuente
Realmente siento que sea una mala solución. He estado buscando un algoritmo para lograr esto en mejor momento, pero no encontré nada por ahora ...
rorlork
Bueno, la complejidad de la tarea requerida debe estar alrededor de O (n ^ 4) a O (n ^ 5), por lo que los tiempos de ejecución largos son un hecho determinado
hoffmale
Creo que debería ser más como O (n ^ 3) en el peor de los casos, al menos con mi algoritmo. De todos modos, estoy seguro de que se puede hacer algo para mejorarlo, como algún tipo de búsqueda de árbol, pero no estoy seguro de cómo se implementaría.
rorlork
Oh sí, O (n ^ 3) es ... tenía un enfoque diferente en mente que hubiera tomado O (n ^ 4), pero ese es un poco inútil ahora xD
hoffmale
usted podría ahorrar una pequeña cantidad de tiempo si cambia el cheque en los dos exteriores para los bucles de i < a.length()que i < a.length - (longestA.second - longestA.first)(lo mismo para jy b.length ()), ya que no tendrá que procesar los partidos más pequeño que el actual más larga
hoffmale
2

R

Parece que terminé de complicar el problema con la solución anterior. Esto es aproximadamente un 50% más rápido (23 segundos en cadenas de 15k) que el anterior y bastante simple.

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)

Esto nunca será un competidor debido al idioma, pero me divertí un poco haciéndolo.
No estoy seguro de la complejidad de la misma, pero en un par de ~ 15k cadenas tarda 43 segundos usando un solo hilo. La mayor parte de eso fue la clasificación de las matrices. Intenté algunas otras bibliotecas, pero sin una mejora significativa.

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)

Método:

  • Crear una matriz de sufijos para cada cadena
  • Ordenar las matrices de sufijos
  • Recorre cada una de las matrices de forma escalonada comparando el comienzo de cada una
MickyT
fuente
Por supuesto, la solución más fácil en R es usar Bioconductor.
archaephyrryx
@archaephyrryx Una solución bioconductora sería divertida.
Sería ... Pero mi lectura rápida de los documentos estaba muy por encima de mi cabeza. Tal vez si entendiera los términos :-)
MickyT
Eliminé mi primer comentario. Por supuesto, puede usar cualquier biblioteca de código abierto que desee para este desafío.