Найти префикс

[Racheengel]

ЗЫ. Вот загуглил и: http://yumei165.blogspot.de/2013/04/longest-common-prefix-c-code.html

Вот Вы рассказывали как начинали с ассемблера и до сих пор следите чтобы код был "нежирный" - и мое сердце радовалось Ну как же Вы не постеснялись привести реализацию с пере-созданием строки на каждой итерации? 

Поиск "готовых решений" засасывает, появляется неуемное желание "жрать", причем все подряд, хорошее/плохое - неважно, главное что "готовое"

Так это просто "первый найденный пример"
Вот Вы его уже оптимизировали, и это хорошо.
Можно оптимировать дальше - например, у Вас постоянно вызывается src0.resize(last); чего можно избежать, если заменить while на for

[Igors]

Так это просто "первый найденный пример"
Вот Вы его уже оптимизировали, и это хорошо.

Оптимизировал? Да я его не видел пока писал   Осуждать гугление конечно глупо, но за таким лазить = полное моральное разложение 

Что там со spirit-реализацией? Видать опять урыл гулять с собачкой..

[m_ax]

Что там со spirit-реализацией? Видать опять урыл гулять с собачкой..

Вы сначало чётко сформулируйте правила определения префикса.. Чтоб по ним можно однозначно сказать, что вот это префикс, а не суффикс там, например..

[Igors]

Вы сначало чётко сформулируйте правила определения префикса.. Чтоб по ним можно однозначно сказать, что вот это префикс, а не суффикс там, например..

Если не доходит стартовый пост, то вот примеры из жизни, сами и формулируйте

1) Есть массив строк без всякого префикса
Hip
RightLeg
LeftArm

2) Добавлено имя и подчеркивание
Zombie_Hip
Zombie_RightLeg
Zombie_LeftArm

3) Добавлено имя и двоеточие
mixamorig:Hip
mixamorig:RightLeg
mixamorig:LeftArm

4) То же но с пробелами
mixamorig : Hip
mixamorig : RightLeg
mixamorig : LeftArm

Возможно будут еще варианты, зависит от приложений которые записывают текстовики.

[m_ax]

сами и формулируйте

Нормально так) Это по-нашему)

Вот накатал на коленке:

Код

C++ (Qt)
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/spirit/include/phoenix.hpp>
 
#include <iostream>
#include <string>
 
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
namespace sw = boost::spirit::standard_wide;
 
int main()
{
    std::string str = "Zombie : Hip ";
    std::string out;
 
    if(qi::phrase_parse(str.begin(), str.end(), qi::lexeme[+qi::alnum] >> qi::omit[qi::char_("_:") >> +qi::char_], sw::space, out))
        std::cout << out << std::endl;
 
    return 0;
}
 
 

[Racheengel]

Думаю, тут можно переносить тему,т.к. это уже совсем не "C/C++"

[Bepec]

c Igors всегда так.

Переход в раздел C++
   Задача.
   Решение проблемы в следующем посте.
   Изменение условий + бла бла бла
Переход темы в раздел говорилка
   Обсуждение непонятно чего, понятное только Igors

[Igors]

Вот накатал на коленке:

Много раз слышал про эту коленку, но так и не понимаю что это? Я всегда пишу одинаково

Код

C++ (Qt)
    if(qi::phrase_parse(str.begin(), str.end(), qi::lexeme[+qi::alnum] >> qi::omit[qi::char_("_:") >> +qi::char_], sw::space, out))
 

Вы первый пост читали? Там популярно написано, что все строки должны начинаться с префикса (т.е. найти наибольшую общую стартовую часть всех строк). Зачем же Вы пытаетесь учесть все возможные варианты разделителей а одной строке? Завтра придет напр Zombie@Hip. Пьющий за ван Гога должен понимать что такое "эмпирическое правило"
 

Обсуждение непонятно чего, понятное только Igors

Вам что-то непонятно - не засоряйте эфир и не мешайте говорить тем кому понятно.  

[m_ax]

Вы первый пост читали? Там популярно написано, что все строки должны начинаться с префикса

Читал, и там нет того, о чём я Вас просил? Если префикс не должен содержать цивры, замените qi::alnum на qi::alpha.

Там популярно написано, что все строки должны начинаться с префикса

Точно, так вот что конкретно подразумевается под префиксом?

(т.е. найти наибольшую общую стартовую часть всех строк).

Что такое наибольшая стартовая часть всех строк?

Зачем же Вы пытаетесь учесть все возможные варианты разделителей а одной строке?

Все возможные? Где? Вы сказали, что разделители могут быть либо _ либо :. Я согласно этим правилам это и представил. 

Завтра придет напр Zombie@Hip.

Пусть приходит, велком) Мне будет достаточно изменить правило и всё..

Не понимаю все эти претензии.. Эх..

[Old]

m_ax, нужно у всех строк коллекции найти (или не найти) общее начало. Это и будет префикс.
Но между префиксом и остальной строкой может быть любой символ, кроме буквы или цифры.
Кстати у ТС нет ни слова о ситуации, когда одна из строк содержит только префикс.

[m_ax]

m_ax, нужно у всех строк коллекции найти (или не найти) общее начало. Это и будет префикс.
Но между префиксом и остальной строкой может быть любой символ, кроме буквы или цифры.
Кстати у ТС нет ни слова о ситуации, когда одна из строк содержит только префикс.

И я так понимаю, что сам список всех возможных префиксов заранее неизвестен?  Если нет, то задача опять же эквивалентна вычленению минимально необходимых правил, которые однозначно выявляют префикс. И чем в этом плане не устраивает spirit? 

[Old]

И чем в этом плане не устраивает spirit? 

От вас ждут готового решения.

[Igors]

И я так понимаю, что сам список всех возможных префиксов заранее неизвестен?  Если нет, то задача опять же эквивалентна вычленению минимально необходимых правил, которые однозначно выявляют префикс. И чем в этом плане не устраивает spirit? 

В первую очередь префикс должен быть общим для всех строк в контейнера. Т.е. это начало всех строк. И лишь дополнительная проверка "префикс не заканчивается на букву/цифру" - для нее spirit совсем необязателен. Чего Вы за него ухватились - не знаю

[poru]

А если так:

Код

C++ (Qt)
std::string GetPrefix(const std::vector<std::string> & vec)
{
    std::string s = vec[0];
 
    auto result = std::find_if(s.begin(), s.end(), [] (char ch) { return !(std::isalpha(ch) || std::isdigit(ch)); });
    if (result == s.end())
        return std::string();       // prefix not found or prefix at end: "Zombie_"
 
    auto distance = std::distance(s.begin(), result);
    if (distance == 0)
        return std::string();       // prefix in beginning: "_Zombie"
 
    std::string prefix = s.substr(0, distance + 1);
    if (std::all_of(vec.begin(), vec.end(), [prefix] (std::string s) { return s.find(prefix) == 0; }))
        return prefix;              // prefix everywhere
 
    return std::string();           // prefix partly
}
 

[Igors]

А если так:

Не гарантируется что сам префикс содержит лишь одну "не букву/цифру", напр такое

Zombie_Elegant_Hip
Zombie_Elegant_RightLeg

допустимо