Перекрытие ключевого слова и слова сравнения

Question

Перекрытие ключевого слова и слова сравнения

Как я могу кодировать, если заявления, которые дают мне следующие результаты:

Ключевое слово = лицо

Слова сравнения (пользовательский ввод) = effac, acer

Несколько примеров, чтобы дать представление о том, что я имею в виду:

 Keyword: face
Match: effac
Overlap: 3 (fac)

Keyword: face
Match: acer
Overlap: 3 (ace)

Keyword: llama
Match: amazing
Overlap: 3 (ama)

Keyword: lame
Match: lament
Overlap: 4 (lame)

Я думаю, что мне нужно использовать substr? Или просто в целом, что я могу сделать, чтобы выяснить, как определить совпадение этих двух сценариев? У меня уже есть готовые функции, мне просто нужно выяснить, какие условия мне нужно поместить в мои операторы if / else, и тело блока кода if / else.

0

algorithm c++overlap

Решение

Другие решения

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

//first case overlap is either in the beginning or the end for both words

count = 0
for i = 0 to word.length - 1
if word[i] == match[i]
count++
else
break;

if count != 0
//output first count letters
else //you dont have your match in the beginning, check for the end
for i = word.length - 1 to 0
if word[i] == match[i]
count++
else
break;

if count != 0
//output last count letters

//second case overlap is at the opposite ends

for i = 0 to word.length - 1
if word[i] == match[match.length - 1 - i]
count++
else
break;

if count != 0
//output first count letters
else //you dont have your match in the beginning, check for the end
for i = 0 to word.length - 1
if word[word.length - 1 - i] == match[i]
count++
else
break;

if count != 0
//output last count letters

0

Источник

Accepted Answer

#include <string>

std::string longestCommonSubstr( std::string& s, std::string& in) {
size_t s_s = s.size();
size_t in_s = in.size();
if ( ( s_s == 0) || ( in_s == 0)) return std::string();
size_t common_s = std::min( s_s, in_s);
for ( size_t i = common_s; i > 0; i--) {
size_t pos_beg = 0;
size_t pos_end = i;
while ( pos_end < s_s + 1) {
std::string searched =  s.substr( pos_beg, pos_end);
size_t found = in.find( searched);
if ( found != std::string::npos) return searched;
++pos_beg;
++pos_end;
}
}
return std::string();
}

использование:

int main(int argc, char** argv) {

std::string me( "face");
std::string ymey( "effac");
std::string res = longestCommonSubstr( me, ymey); // res is "fac"if ( !res.empty()) {
// found
}
return 0;
}

1