Задачка со строками.

[незваный гость]

C0rWin писал(а):

Если есть неясности в приведенном мной отрывке, скажите, что именно не понятно и я попытаюсь объяснить.

Попробуйте описать алгорифм словами, избегая идентификаторов. Примерно так, как я описал мой. Согласитесь, моя программа достаточно прямолиейно следует моему описанию.

[незваный гость]

Sanyok писал(а):

А почему эта задача должна решаться за время не меньшее чем T(n^3)? Разве есть какие-то принципиальные запреты на то, что ее можно решить за меньшее время(например, T(n^2))?

Я не думаю, что было задано требование не решать за время лучшее чем T(n^3). Я его прочитал как "время не хуже, чем T(n^3), память константа". С точки знрения ограничения по памяти варианты, предложенные maxal, скорее всего не пройдут.

[C0rWin]

Цитата:

Попробуйте описать алгорифм словами, избегая идентификаторов. Примерно так, как я описал мой. Согласитесь, моя программа достаточно прямолиейно следует моему описанию.

Что же попробую. Для начала я просто определяю какая из строк больше и какая меньше. Потом начинаю с более короткой. Так же удаляются все пробелы. Ну и потом начинаю с первого символа более короткой строки, прогоняю указатель по второй строке до тех пор пока не встречу похожий символ, как только встретил такой начинаю смотреть сколько их всего таких похожих, одновремено запоминаю индекс где произошло это совпадение. Если получившаясь последовательность получилась самая большая то я ее запоминаю, возвращаю указатель более маленькой строки на начало и продолжаю до конца, ну и в конце увиличиваю указатель на следующий символ короткой строки и начинаю все заново.

Это примерное описание без мелких не существенных деталей, который и так можно увидеть из приведенного кода.

Кстати на счет сложности, то мой друг с помощью простых циклов решил эту задачу за T(n) (это я так к слову).

[C0rWin]

Вот еще решение не скажу, что оно простое и понятное, зато проверенное и работает за T(n^2). Это в продолжение на тему решение предложеное моим другом.

void findMaxSub(char *str1, char *str2)
{
   int counter, maxc=0, shifts=0, maxs=0, maxl;
   int i,j,k=0;
   int n=strlen(str2), m=strlen(str1);

   for(i=0;i<n;i++) {
      k=0;
      for(j=0,counter=0;j<shifts && j<m;j++) {
         if(str1[j]==str2[j])
            if(++counter > maxc) {
               if(!k) {
                  maxs=shifts;
                  maxl=j-counter+1;
                  k=1;
               }
               maxc=counter;
            }
         if(str1[j]!=str2[j]) {
            counter=0;
            k=0;
         }
      }
      k=0;
      for(counter=0;j<m;j++) {
         if(str1[j]==str2[j])
            if(++counter > maxc) {
               if(!k) {
                  maxs=shifts;
                  maxl=j-counter+1;
                  k=1;
               }
               maxc=counter;
            }
         if(str1[j]!=str2[j]) {
            counter=0;
            k=0;
         }
      }

      for(shifts++,j=n-1;j>0;j--)
         swap(str2+j,str2+j-1);
   }

   if(maxc>0) {
      for(i=0;i<maxs;i++)
         for(j=n-1;j>0;j--)
            swap(str2+j,str2+j-1);
      for(i=0;i<maxc;i++)
         printf("%c", str2[i+maxl]);
   }

}

[evgeny]

C0rWin
Скажите а как Вы понимаете, что Ваше решение "проверенное"?
Оба приведенных Вами кода основаны на одной и той же ошибке -
если вы нашли совпадение каких-то K символов, а потом различие, то вы начинаете искать дальше начиная с места, где различие возникло. На самом деле нало продолжать искать со следующего символа.
Для Вашего первого варианта кода (который на стр 1)
пара строк ("aab", "aaab") -> "ab"
Ваш второй вариант для строк
("ababb", "abb") -> "ab"


Разве сложно проверить Ваш "алгоритм" на 10000 случайных пар строк (можно только из букв A и B) перед тем как выкладывать его на форум ?

[незваный гость]

Я еще не разу не видел не-"простых циклов". Все циклы простые, но это так, из общей язвительности.

Я прочитал решение Вашего друга, и оно (в основном) работает. В основном, поскольку модифицирует строки. В нынешних процессорах это не всегда возможно, и контролируется (я получил ошибку времени выполнения write access denied). Хотя функция и не специфицирет указатели на константы, строки по сути таковыми являются. Беда С то, что эта проблема маскируется компилятором.

Другой его недостаток -- то, что алгоритм не совсем корректен. А именно, findMaxSub("123456bcaa", "aadef") подстроки "аа" не находит. Это поправимо, но без правки -- bug.

Попробую переписать программу по своему разумению (функция out(ss, count) выдает результат):

const char* mss; // max substring;
int mc; // max count

void find0(const char* s1, const char* s2) {
  int i, shift, count;
  const char* ss;

  for (shift = 0; s2[shift] != 0; ++shift) {
    // сравниваем строку s1 со сдвинутой s2
    // находим за один проход все совпавшие подстроки

    // при несовпадении, запоминаем указатель на следующий символ и срасываем счетчик
    // при совпадении -- наращиваем счетчик 
    // (указатель на начало установлен при предыдущем несовпвдении)
    ss = s1; count = 0;
    for (i = 0; s1[i] != 0 && s2[i+shift] != 0; ++i) {
      if (s1[i] == s2[i+shift]) {
        ++count;
      } else {
        if (count > mc) {
          mc = count; mss = ss;
        }
        count = 0;
        ss = s1 + (i+1);
      }
    }
    if (count > mc) {
      mc = count; mss = ss;
    }
  } 
}

void find(const char* s1, const char* s2) {
  mss = s1; mc = 0;
  find0(s1, s2);
  find0(s2, s1);
  out(mss, mc);
} 

В основном, по мотивам решения Вашего друга. Глобальные переменные -- из-за того, что лень было структуры описывать, да указатели на них туда-сюда таскать. Скорость - действительно T(n^2), ну да тут это очевидно. Поиск (find0())повторяется два раза, фактически эмулируя отрицательный сдвиг между строками.

[C0rWin]

Цитата:

Разве сложно проверить Ваш "алгоритм" на 10000 случайных пар строк (можно только из букв A и B) перед тем как выкладывать его на форум ?

Мда..... А что, это кому либо помешало? Или вы при виде не правильного алгоритма начинаете плохо себя чувствовать? Я конечно дико извиняюсь, но я просто подумал, что не плохо было бы услышать критику и если есть ошибки.... Я ведь если честно не специально ошибся и не заметил ошибку, а просто ошибся изначально в логике, вот и все. И Вам огромное спасибо за указку. В результате пришлось немного модернизировать код и добавить еще один цикл. В итоге получилось, что овчинка выделки не стоит.
Т.е. самое нормальное решение какое я только видел до сегоднешнего дня это с проходом в трех циклах.

[незваный гость]

evgeny писал(а):

Разве сложно проверить Ваш "алгоритм" на 10000 случайных пар строк (можно только из букв A и B) перед тем как выкладывать его на форум ?

Мне очень интересно. Ну, 10000 строк нагенерировать не фокус. Фокуса два других. Первый, как проверить, что найденная наибольшая подстрока -- действительно наибольшая. То есть, сгенерированные строки не содержат результата. Более того, результат не обязан быть единственным. Поэтому, прогнав на 10000 примерах Вы просто ничего не узнаете. (Не имея альтернативного метода получения результата.)

Фокус второй -- прогнав 10000 тестов Вы получите некоторую уверенность, что программа работает. Да вот беда -- существует вероятность достаточно редкой ситуации, которая покрыта не будет. Обычно контрпримеры приходиться аккуратно конструировать, базируясь на алгоритме.

Могу порекомендовать Myers G.J. — Art of Software Testing.

И, хочу добавить, что C0rWin выкладывал свою программу для обсуждения, а вовсе не как ответ на чей-то вопрос. Так какие к нему могут быть претензии? Ну ошибся человек -- так совета же спрашивал, а не говорил -- "делай как я".

C0rWin писал(а):

Т.е. самое нормальное решение какое я только видел до сегоднешнего дня это с проходом в трех циклах.

Мне кажется, мое решение выше работает... с двумя циклами... Хотя 10000 тестов и не гонял...

[C0rWin]

незванный гость писал(а):

\

Попробую переписать программу по своему разумению (функция out(ss, count) выдает результат):

const char* mss; // max substring;
int mc; // max count


.........................................
.........................................
.........................................


void find(const char* s1, const char* s2) {
  mss = s1; mc = 0;
  find0(s1, s2);
  find0(s2, s1);
  out(mss, mc);
} 

Ну и по мотивам вашего же преобразования (доп. функция которая запускает две строки меня их места) решила баг и в моем случае, ну еще нужно было просто исключить проверку на наибольшую строку, т.е. делать поиск не зависимо от длины строк, а потом просто проверять в разном порядке. Вроде выдает верные результаты. Опять же пока нет 100% уверености, так что буду рад любому контр-примеру.
Так что доп. цикл не очень то как оказалось и нужен. Но опять таки исходя из строго условия задачи варинты с тремя циклами самый верный ибо в остльных не выполняется условия с памятью.

[незваный гость]

C0rWin писал(а):

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

Может быть. У меня эти два вызова -- явление концептуальное. Предположим, максимальная строка начинается со смещения i в первой строке, и со смещения j во второй. Тогда либо j - i >= 0, либо i - j >= 0. Первый случай находиться первым вызовом, второй -- вторым (поскольку shift всегда неотрицателен).

C0rWin писал(а):

Вроде выдает верные результаты. Опять же пока нет 100% уверености, так что буду рад любому контр-примеру.

Я тестировал свою программу. Однако моя уверенность в ней основана на доказательстве ее правильности. Если Вам захочется повторить мои рассуждения, то инвариант внутреннего цикла ss[0 ... count-1] -- текущая найденная подстрока при данном смещении.

C0rWin писал(а):

Но опять таки исходя из строго условия задачи варинты с тремя циклами самый верный ибо в остльных не выполняется условия с памятью.

А почему? O(1) -- это и 100 тоже. Программа использует ограниченную память, не зависящую от длины сравниваемых строк. Если есть опасения с вызовом, так ведь он не рекурсивный. В конце концов, можно текстуально подставить find0(), получив более длинный текст, но убедившись, что используемая память O(1).

[C0rWin]

Поправте меня если я ошибаюсь, но Си работает со строками не совсем как Паскаль и поэтому объявление типа:

const char *ss;

является не совсем корректным так как Си воспринимает это как массив под который он выделяет не малое кол-во памяти, а по сему на мой взгляд более правильно было бы воспользоваться динамическим распределением памяти, нужного нам размера, в данном случае по длине строки т.е. получаем O(n). Если я не прав то поправте меня.

[незваный гость]

C0rWin писал(а):

Поправте меня если я ошибаюсь, но Си работает со строками не совсем как Паскаль и поэтому объявление типа:

const char *ss;

является не совсем корректным так как Си воспринимает это как массив под который он выделяет не малое кол-во памяти, а по сему на мой взгляд более правильно было бы воспользоваться динамическим распределением памяти, нужного нам размера, в данном случае по длине строки т.е. получаем O(n). Если я не прав то поправте меня.

Поправляю: это объявление -- указатель (pointer) на константную литеру (или массив оных). Примерно соответствует паскалевскому

type
   pchar = ^ char;
var
   ss: pchar;

Соответственно, никакого выделения памяти под массив и динамического распределения памяти не происходит, кроме как на сам указатель. (Обратите внимание как он присваивается: ss = s1 + (i+1); -- пример адресной арифметики)

Указатели в С, Вы правы, используются и для динамически размещаемых объектов. Но одно из характерных использований -- это указатель, "бегущий" по массиву. В С++ в STL эта идиома употребления указателя была расширена до итератора -- синтаксически похожего (в использовании) на указатель типа.

[photon]

Жуть, как трудно разбираться в чужих кодах, особенно написанных на незнакомом языке... Но, если я правильно понял, чуть-чуть можно ускорить работу: если Вы нашли совпадение строк длиной N и она оборвалась, то необязательно вести сравнение до конца - последние N-символов уже можно не сравнивать - трудно объяснить тонкости,которые я вижу, но нужно тут быть внимательным

PS Я скромно считаю, что неплохо владею алгоритмией, но не знаю языков (то есть знаю, но другие), в частности С, пожалуйста, если не сложно, пишите комментарии построчно.

[незваный гость]

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

Есть еще одна опущенная оптимизация. При втором проходе можно было бы пропускать shift == 0, поскольку он уже был пройден при первом проходе.

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

Куда более интересным ресурсом оптимизации является шаг при внутреннем проходе строк. Идея состоит в том, что нормально несовпадения куда более часты, чем совпадения. Поэтому, если найдено совпадение длины mc, то, пока не найдены совпадающие символы, можно идти с шагом mc+1 (в чем-то следуя одной из идей алгоритма Бойер-Мура).

Но все это, разумеется, приводит к удлинению и усложнению кода. Если же оптимизация так важна, то наверное, надо-таки переходить к суффиксным деревьям.