Блог

Проблема:

У меня есть 3 строки s1, s2, s3. Каждая содержит ненужный текст с обеих сторон, с определяющим шаблоном в центре: text1 number1 . number1 увеличивается на 2 в каждой строке. Я хочу извлечь text1 number1 .

Я уже написал код для поиска number1

Как бы я расширил функцию LCS, чтобы получить text1?

 #include <iostream>

const std::string longestCommonSubstring(int, std::string constamp; s1, std::string constamp; s2, std::string constamp; s3);

int main(void) {
    std::string s1="hello 5", s2="bolo 7", s3="lo 9sdf";
    std::cout << "Trying to get "lo 5", actual result: "" << longestCommonSubstring(5, s1, s2, s3) << '"';
}

const std::string longestCommonSubstring(int must_include, std::string constamp; s1, std::string constamp; s2, std::string constamp; s3) {
    std::string longest;

    for(size_t start=0, length=1; start   length <= s1.size();) {
        std::string tmp = s1.substr(start, length);
        if (std::string::npos != s2.find(tmp) amp;amp; std::string::npos != s3.find(tmp)) {
            tmp.swap(longest);
              length;
        } else   start;
    }

    return longest;
}
  

Пример:

Из "hello 5" , "bolo 7" , "lo 9sdf" я хотел бы получить "lo 5"

Код:

Я смог написать простую функцию LCS (тестовый пример), но у меня возникли проблемы с написанием этой модифицированной.

Допустим, вы ищете шаблон * n, * n 2, * n 4 и т.д. И у вас есть следующие строки: s1= «привет 1, пока 2, чао 1», s2 = «привет 3, пока 4, чао 2» и s3 = «привет 5, пока 6, чао 5». Тогда будет сделано следующее:

 //find all pattern sequences
N1 = findAllPatterns(s1, number);
 for i = 2 to n:
  for item in Ni-1:
   for match in findAllPatterns(si, nextPattern(item))
    Ni.add([item, (match, indexOf(match))]);

//for all pattern sequences identify the max common substring
maxCommonLength = 0; 
for sequence in Nn:
 temp = findLCS(sequence);
 if(length(temp[0]) > maxCommonLength):
  maxCommonLength = length(temp[0]);
  result = temp;

return resu<
  

`
Первая часть алгоритма определит последовательности:
[(1, 6), (3, 6), (5, 6)], [(1, 19), (3, 6), (5, 6)], [(2, 12), (4, 12), (6, 12)]

Вторая часть определит: [«привет 1», «привет 3», «привет 5»] как самые длинные подстроки, соответствующие шаблону.

Алгоритм можно дополнительно оптимизировать, объединив две части и отбросив ранние последовательности, которые соответствуют шаблону, но являются неоптимальными, но я предпочел представить его в двух частях для большей наглядности.

— Редактировать исправленный блок кода

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

Я буду называть ваши строки s[0] , s[1] и т.д. Набор longest = INT_MAX . Для каждой строки s[i] (i > = 0) просто:

• Найдите, где number1 2 * i встречается в s[i] . Предположим, это происходит в позиции j .
• Если (i == 0) j0 = j; else
  • для (k = 1; k <= j amp;amp; k <= самый длинный amp;amp; s[i][j — k] == s[0][j0 — k]; k) {}
  • самый длинный = k;

В конце longest будет указана длина самой длинной подстроки, общей для всех строк.

По сути, мы просто сканируем в обратном направлении от точки, где мы находим число, ищем несоответствие соответствующему символу в вашем s1 (моем s[0] ) и отслеживаем, в какой подстроке самая длинная совпадающая на данный момент longest — это может оставаться неизменным или уменьшаться с каждой новой строкой, которую мы просматриваем.

Вместо того, чтобы пытаться модифицировать внутренности алгоритма LCS, вы могли бы взять его выходные данные и найти их в s1. Оттуда ваш номер будет расположен со смещением длины выходного файла плюс 1.

Написал свое собственное решение:

 #include <iostream>
#include <string>
#include <sstream>
#include <vector>

typedef std::pair<std::pair<std::string, std::string>, std::pair<std::pair<std::string, std::string>, std::pair<std::string, std::string>>> pairStringTrio;
typedef std::pair<std::string,std::pair<std::string,std::string>> stringPairString;

stringPairString longestCommonSubstring(const pairStringTrioamp;);
std::string strFindReplace(const std::stringamp;, const std::stringamp;, const std::stringamp;);

int main(void) {
        std::string s1= "6 HUMAN ACTIONb", s2="8 HUMAN ACTIONd", s3="10 HUMAN ACTIONf";
        pairStringTrio result = std::make_pair(std::make_pair(s1, "6"), std::make_pair(std::make_pair(s2, "8"), std::make_pair(s3, "10")));

        stringPairString answer = longestCommonSubstring(result);
        std::cout << '"' << answer.first << ""t"" << answer.second.first << ""t"" << answer.second.second << '"';
}


stringPairString longestCommonSubstring(const pairStringTrio amp;foo) {
        std::string longest;

        for(size_t start=0, length=foo.first.first.size()-1; start   length <= foo.first.first.size();) {
                std::string s1_tmp = foo.first.first.substr(start, length);
                std::string s2_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.first.second);
                std::string s3_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.second.second);

                if (std::string::npos != foo.second.first.first.find(s2_tmp) amp;amp; std::string::npos != foo.second.second.first.find(s3_tmp)) {
                        s1_tmp.swap(longest);
                          length;
                } else   start;
        }

        return std::make_pair(longest, std::make_pair(strFindReplace(longest, foo.first.second, foo.second.first.second), strFindReplace(longest, foo.first.second, foo.second.second.second)));
}

std::string strFindReplace(const std::string amp;original, const std::stringamp; src, const std::stringamp; dest) {
        std::string answer=original;
        for(std::size_t pos = 0; (pos = answer.find(src, pos)) != answer.npos;)
                answer.replace(pos, src.size(), dest);
        return answer;
}