Russian Qt Forum

Добрый день

Вроде сопливая задачка, а писать приходится не так уж мало. Есть std::vector<std::string> нужно узнать, начинаются ли все строки с какого-то имени (префикса). напр

C++ (Qt)
Zombie_Hip 
Zombie_RightLeg 
Zombie_LeftArm 
..
// префикс Zombie_
 

Ну и требования "здравого смысла" - префикс не может оканчиваться буквой или цифрой (напр если все начинаются с "A", но это еще не префикс). Вот собсно и все - но как-то "не ложится". Прошу блеснуть  :)

Спасибо

Не блесну, простой проход по строке с окончанием на "не букве не цифре", а потом сравнение полученной строки в следующих итерациях вас не устраивает?

Тут надо уточнить.
Префикс известен заранее? Т.е. надо искать конкретное вхождение?
Или префикс надо выделить из набора строк?
Тогда придется сравнивать все строки до ближайшего несовпадения и потом брать минимальный найденный индекс.
Строка от 0 до этого индекса и будет префиксом.

C++ (Qt)
#include <iostream>
#include <vector>
#include <algorithm>
 
 
    std::vector<std::string> strings;
    strings.push_back("Zombie_Hip");
    strings.push_back("Zombie_RightLeg");
    strings.push_back("Zombie_LeftArm");
 
    bool all = std::all_of(strings.begin(), strings.end(), [](std::string str){ return str.find("Zombie_") == 0; });
    std::cout << all;  // 1
 
 
    strings.push_back("Vasya_LeftArm");
    all = std::all_of(strings.begin(), strings.end(), [](std::string str){ return str.find("Zombie_") == 0; });
    std::cout << '\n';
    std::cout << all;  // 0
 

Или, руками в цикле:

C++ (Qt)
bool my_all_of(const std::vector<std::string>& strings, const std::string& prefix) {
    for (std::string text: strings) {
        if (text.find(prefix) != 0) {
            return false;
        }
    }
 
    return true;
}

Если я неправильно понял и нужно сначала найти префикс, тогда нужно завести правило по которому префикс находится, например:
Набор символов a-zA-Z до первого встреченного символа '_' слева от строки. Тогда проблем с нахождением не будет

Конечно надо найти, вот (эмпирическое) правило

Если перевести в регулярку, то кажется получается такое правило: ^([\da-zA-Z]+[^\da-zA-Z]+) (https://regex101.com/r/eY4cM1/1)

1. Сравниваем первую строку с остальными до ближайшего несовпадения.
2. Берем минимальный найденный индекс.
3. Смотрим от него "назад" до первого символа, не являющегося буквой или цифрой.
4. профит )

:)

Не, ну "принципиально" я со всем этим согласен. Но вот реализация выходит какой-то длинной и занудной  :'(

ну, а шо делать)
да в принципе не так и много писать, если подумать.
пара простых циклов.
дольше обсужаем, как мне кажется :)

Ну ожидаемо, что уж там.. задача слегка вышла за пределы обычного парсига тел. номеров и тут же возникла целая тема на форуме..
Сформулируйте грамотно правила для разбора префиксов и spirit вам в помощь..) 

Он имеет в виду - сделайте так, чтобы код был красивым, чтобы его было мало, чтобы он покрывал все сценарии использования, чтобы был самодокументируемым на сто %, чтобы использовать его мог человек без знания ЯП, максимально кроссплатформенным, максимально оптимизированным под каждую платформу, но без платформозависимого кода и при копировании в любое место любого исходника на любом языке программирования выполнял свою задачу.

Ах да, забыл - и ещё чтоб нравится Igors просто так :D

И и и...и? На спирите это не красиво? Не читабельно? Не переносимо? Или много кода? Да, серьёзно? Ну предложите свой вариант, а мы посмотрим) 

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

во-первых - это, по сути, другой язык.
во-вторых - это дополнительная зависимость.
в-третьих - хз что там за таргет-платформа, может быть важен вопрос переносимости.
в-четвертых, работы на 10 минут - а уже день обсуждаем :)

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

Ну так чего ж Вы не пишете?  :)

Придумалось, вот опорная ф-ция

C++ (Qt)
bool TestMatch( std::string & src0, const std::string & src1 )
{
// find matched strings start
	size_t len, maxLen = qMin(src0.size(), src1.size());
	for (len = 0; len < maxLen; ++len)
		if (src0[len] != src1[len]) break;
	src0.resize(len);
 
// src0 end can't be a letter or digit
	while (src0.size()) {
		size_t last = src0.size() - 1;
		QChar ch = src0[last];
		if (ch.isLetter() || ch.isDigit())
			src0.resize(last);
		else
			break;
	}
	return src0.size() > 0;
}
 

Именно первый аргумент по неконстантной ссылке - тогда все сопли уходят

C++ (Qt)
std::string GetPrefix( const std::vector<std::string> & vec )
{
  if (vec.size() < 2) return std::string();
  std::string match = vec[0];  // копируем первую строку
 
  for (size_t i = 1; i < vec.size(); ++i)
    if (!TestMatch(match, vec[i])) break;
 
 return march;
} 

Причем тут спырыт ??? Ну да ладно, "назвались груздем" - предъявляйте решение на spirit

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

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

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

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

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

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

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

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

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

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;
}
 
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А если так:

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
}
 

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

Я бы строил 256ричное дерево. Если детей ровно 1, то префикс общий.

Вернее, оно даже в список вырождается.