Максимальное количество последовательных общих элементов в двух списках строк [дубликат]

Question

Максимальное количество последовательных общих элементов в двух списках строк [дубликат]

Gson легко учиться и реализовывать, что нам нужно знать, следуют двум методам

toJson () - Преобразование Java-объекта в формат JSON
fromJson () - преобразовать JSON в объект Java

`

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import com.google.gson.Gson;

public class GsonExample {
    public static void main(String[] args) {

    Gson gson = new Gson();

    try {

        BufferedReader br = new BufferedReader(
            new FileReader("c:\\file.json"));

        //convert the json string back to object
        DataObject obj = gson.fromJson(br, DataObject.class);

        System.out.println(obj);

    } catch (IOException e) {
        e.printStackTrace();
    }

    }
}

`

4

python string list

задан Milano Slesarik 3 July 2014 в 08:32

1 ответ

Другие вопросы по тегам:

python string list

Похожие вопросы:

score 8 · Accepted Answer

Вы можете легко перенастроить LCS в LLCS:

def lcs_length(a, b):
    table = [[0] * (len(b) + 1) for _ in xrange(len(a) + 1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1] + 1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]

Демо:

>>> a=[1,2,6,5,4,8]
>>> b=[2,1,6,5,4,4]
>>> lcs_length(a, b)
4

Если вы хотите самую длинную общую подстроку ( другая, но связанная с этим проблема, когда подпоследовательность смежна), use:

def lcsubstring_length(a, b):
    table = [[0] * (len(b) + 1) for _ in xrange(len(a) + 1)]
    l = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                table[i][j] = table[i - 1][j - 1] + 1
                if table[i][j] > l:
                    l = table[i][j]
    return l

Это очень похоже на подход динамического программирования lcs_length, но мы отслеживаем максимальную длину, найденную до сих пор (поскольку он больше не гарантирован, что последний элемент в таблице является максимальным).

Это возвращает 3:

>>> lcsubstring_length(a, b)
3

Вариант разреженной таблицы, который не должен отслеживать все 0 s:

def lcsubstring_length(a, b):
    table = {}
    l = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                table[i, j] = table.get((i - 1, j - 1), 0) + 1
                if table[i, j] > l:
                    l = table[i, j]
    return l