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

[C0rWin]

Задача состоит в следующем. Даны две строки. Требуется определить наибольшую общую подстроку, которая содержится в обеих строках и вывести ее на экран. Требование к решению O(1), T(n^3). Подскажите решение, т.е. мне даже не столько решение нужно сколько возможный алгоритм решения этой задачи. Реализация задачи на Си. Заранее благодарен.

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

А в лоб? (Это не вызов, а подход к решению). То есть, честно перебираем все подстроки начинающиеся с индекса $i$ в первой строке, $j$ во второй, и ищем их общую длину, запоминая ммаксимальную. Акурат заказанные характеристики.

[C0rWin]

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

[Werwolf]

Нужно некоторое уточнение, например если ввели qweraty и erwty, то что будет ответом: erty или (er или ty)? То есть подстрока должна идти одним куском или же нет? Если одним куском, то перебираем все подстроки из строки 1 по убыванию длины и проверяем их вхождение в строку 2(оптимизация: строка 1 - короче). Если же символы общей подстроки могут идти в исходных строках вразброс, но в том же порядке, то задача становится несколько сложнее и тут используется динамическое программирование. В этом случае надо посмотреть статью на решение этой задачи на винте. Уточните, пожалуйста, постановку задачи.

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

C0rWin писал(а):

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

Шутить изволите-с? Я же сказал -- запоминая лучшую найденную подстроку. Но если Вы так уверены, что я не прав -- контр-пример на форум, и я проверю. А предъявы, что не работает, без контр-примера, как-то звучат слабовато, милостливый государь.

[Sanyok]

Начните с одинаковых букв.
К примеру, берем первую букву в первой строке, ищем ее в другой, находим N вхождений. Если N = 0, то переходим ко второй букве, иначе - берем вторую букву в первой строке и ищем ее во второй строке по соседству справа от уже найденных вхождениий(если мы ведем сканирование слева направо). Находим еще N2 вхождений (это уже будут строки из 2-х букв). И т.д.

[C0rWin]

Уточняю задачу:
первая строка: "Какая сегодня прекрасная погодка"
второя строка: "Год назад я прекратил курить"

ответом должна быть строка (пробелы не считаются, так как же как и регистр букв):
"япрекра".

Цитата:

Шутить изволите-с? Я же сказал -- запоминая лучшую найденную подстроку. Но если Вы так уверены, что я не прав -- контр-пример на форум, и я проверю. А предъявы, что не работает, без контр-примера, как-то звучат слабовато, милостливый государь.

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

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

C0rWin писал(а):

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

Отчего же, иногда можно. Описание достаточно конкретно, чтобы оценить, что (a) работает / не работает, (b) потребляет конечную, не зависящую от длин строк память, и (c) заверщает работу за время, пропорциональное кубу длины строк.

C0rWin писал(а):

Просто приведу пример не связанный, но похожий на твой ответ, если на вопрос как посчитать сколько будет 2+2 ответ 4 не является коректным так как он не отвечает на заданный вопрос(я понимаю, что утрировал, но надеюсь так понятнее).

Мне теперь совсем не понятно. Я описал алгорифм решения. Я конечно понимаю, что фраза "перебираем все индексы" написана, конечно, не на алгоритмическом языке, но ведь я описываю алгорифм, а не программу пишу. "Запоминая" тоже конечно, неформальное утвержнение, но вполне формализуемое. Согласитесь, ожидать программу машины Тьюринга (абсолютно формальное выражение алгорифма) не логично. Лично я не готов.

2+2 не поясняет ничего, поскольку я дал Вам алгорифм, а не подстроку.

~~~~~

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

[C0rWin]

To: "незванный гость" Я извиняюсь за свои выпадки, я просто должен был пояснить, что у меня не совсем получилось реализовать предложенный Вами способ, и он мне пришел в голову один из первых и я тоже видел программы работающие по заданому алгоритму. Похоже знать и понимать это не то же что и реализовать. Мне нужно было пояснить просто, что в этом тривиальном случае мне нужны некоторые пояснения, еще раз сорри.

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

void find_max_substr(char *str1, char *str2)
{
   int count=0, m_count=0, i, index=0, m_index=0;

   char *s1, *s2, *tmp1, *tmp2;


   s1=(strlen(del_space(str1))<strlen(del_space(str2)))?del_space(str1):del_space(str2);
   s2=(strlen(del_space(str1))<strlen(del_space(str2)))?del_space(str2):del_space(str1);


   tmp2=s2;


   while (*s1!='\0')
    {
      tmp1=s1;

      while (*tmp2!=*tmp1&&*tmp2!='\0')
       {
         index++;
         tmp2++;
       }

      if (*tmp2=='\0')
       {
         index=0;
         s1++;
         tmp2=s2;
         continue;
       }

      while (*tmp2==*tmp1&&tmp1!='\0'&&tmp2!='\0')
       {
         count++;
         tmp1++;
         tmp2++;
       }

      if (count>m_count)
       {
         m_count=count;
         count=0;
         m_index=index;
       }
      else
       {
         index+=count;
         count=0;
       }

      if (*tmp1=='\0'||*tmp2=='\0')
       {
         index=0;
         tmp2=s2;
         s1++;
         continue;
       }
    }

   for (i=0; i<m_count; i++)
    printf("%c", *(s2+m_index+i));

}

Спасибо всем кто натолкнул на идею.

[C0rWin]

Я ошибаюсь или мое решение получилось за T(n^2)?

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

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

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

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

Во-вторых, мне кажется, Вы некорректно сравниваете указатели с литерами в:

C0rWin писал(а):

while (*tmp2==*tmp1&&tmp1!='\0'&&tmp2!='\0')

Я думаю, Вы потеряли "звездочки".

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

Могу предложить Вам свой вариант решения:

void find(const char* s1, const char* s2) {
  int i, j, k; // текущие индексы и длина
  int im = 0, jm = 0, km = 0; // максимальные индексы и длина

  for (i = 0; s1[i] != 0; ++i) {
    for (j = 0; s2[j] != 0; ++j) {
      for (k = 0; s1[i +k] != 0 && s1[i+k] == s2[j+k]; ++k) {
      }
      if (k > km) {
        im = i; jm = j; km = k;
      }
    }
  }
  for (i = im; i < im + km; ++i) {
    putc(s1[i]);
  }
}

[Sanyok]

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

[C0rWin]

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

[maxal]

Динамическое программирование в данном случае даст алгоритм сложности O(n^2).
А суффиксные деревья дадут алгоритм сложности O(n).

См. http://en.wikipedia.org/wiki/Longest_co ... ng_problem
и также главу 10 в книге Шеня "Программирование: теоремы и задачи" ftp://ftp.mccme.ru/users/shen/progbook2/progbookpdf.zip