Нахождение общей части слов, Пара задач Опции

[Patam]

1. Для задаваемой строки найти все содержащиеся в ней слова и распечатать наибольшую общую часть этих слов.
Пример:
Для строки
мирный примирить перемирие мирить
Общая часть слов - мир.
2. Найти в задаваемой строке содержащиеся в ней корни и распечатать для каждого корня однокоренные с ним слова.
Пример:
Для строки
народ мирный родник мир родина род мирить
Корни____Однокоренные слова
мир______мирный мирить
род______народ родник родина

Хелп плз.

Сообщение отредактировано: Patam - 19.04.2007 20:08

[Lapp]

По п.1 примерно ясно. Задачка неплохая. Вот, я набросал решение..
Ищется самая большая общая подстрока. Если таковых больше одной, найдена будет первая. Как сделать нахождение всех - надо подумать..
Регистр (большие-маленькие буквы) не приводится.
Разделителем слов считаю пробел, но это легко исправить, если нужно - достаточно добавить нужные символы в множество Dividers.

;

var
  s,w,r,t:string;
  i,j,k,kx,n:integer;

function GetWord(s:string; var i:integer; var w:string):boolean;
var
  j:integer;
begin
  while (i<Length(s))and(s[i] in Dividers) do Inc(i);
  j:=i;
  while (j<Length(s))and not(s[j+1] in Dividers) do Inc(j);
  w:=Copy(s,i,j-i+1);
  GetWord:=i<=Length(s);
  i:=j+1;
end;

begin
  s:='смирение примирить перемирие мирный мирить';
  n:=1;
  GetWord(s,n,w);
  while GetWord(s,n,t) do begin
    kx:=0;
    r:='-Nothing-in-common-';
    for i:=1 to Length(w) do begin
      j:=1;
      while j<=Length(t) do begin
        k:=0;
        while (i+k<=Length(w))and(j+k<=Length(t))and(w[i+k]=t[j+k]) do Inc(k);
        if k>kx then begin
          r:=Copy(t,j,k);
          kx:=k
        end;
        j:=j+k+1
      end
    end;
    w:=r
  end;
  WriteLn('Root is: ',r);
  ReadLn
end.

А вот с пунктом 2 не знаю, как быть. Одновременно отыскивать корни, как-то разделяя слова на группы однокоренных?.. это задача неслабая.. Или же список корней задан? Если да, тогда нет проблем.

[Patam]

Список корней задан

[мисс_граффити]

Если да, тогда нет проблем.

не уверена...
даны корни: лист, точ.
точка точит листочек
все три - однокоренные?


а еще есть корни с чередованием (гар-гор, зар-зор)
то есть "пригорел" и "загар" - однокоренные, а "горный" не имеет к ним отношения.
или "мир", "мирный" | "замереть", "замирать".
разделение должны быть именно таким, а не "мир", "мирный", "замирать" | "замереть"

есть еще корни из одной буквы - с ними что делать?

так что вопрос - что понимается под корнем? если просто слог, то проблем нет, а если именно четко определяемая морфема...

[Lapp]

даны корни: лист, точ.
точка точит листочек
все три - однокоренные?
...
а еще есть корни с чередованием (гар-гор, зар-зор)
...
есть еще корни из одной буквы - с ними что делать?

мисс_граффити, ты, мне кажется, переоцениваешь обычную задачу на программирование. Это не есть реальный русский язык, это просто похоже. Кстати, в названии темы ничего про корни нету. Я использую эту терминологию для упрощения общения .
Полагаю, что реальные данные, на которых будет проверяться решение, не будут включать перечисленных тобой случаев. Кроме того, первый случай у тебя с наложением "корней", а второй просто противоречит условию задачи . Третий, полагаю, является вырожденным..

Добавлено через 3 мин.
По этому же поводу: не так давно я помогал решить задачу на перенос слов. Там были некоторые правила для переноса, которые неплохо вписывались в РЯ во многих случаях. Но конечно, не во всех!.. Тем не менее задача прекрасно демонстрировала принципы программирования. Так же и эта..

Добавлено через 18 мин.
Жаль только, автор темы немногословен..
Видимо, ему достаточно оказанной помощи..

[мисс_граффити]

мисс_граффити, ты, мне кажется, переоцениваешь обычную задачу на программирование. Это не есть реальный русский язык, это просто похоже. Кстати, в названии темы ничего про корни нету. Я использую эту терминологию для упрощения общения .
Полагаю, что реальные данные, на которых будет проверяться решение, не будут включать перечисленных тобой случаев. Кроме того, первый случай у тебя с наложением "корней", а второй просто противоречит условию задачи . Третий, полагаю, является вырожденным..

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

да, скорее всего тесты будут "без заморочек". это я зря... просто полдня пытаюсь угадать, на каком тесте моя программка не работает. вот и увлеклась... *смущенный смайлик*

но все же...
где-то сказано, что наложения быть не может? хорошо.
корни: лист, очк
очки очкарик листочки

противоречие... чему противоречит-то?

вырожденный, но это не значит недопустимый...

ждем автора

[Lapp]

> по пунктам
По пунктам - так по пунктам..

> стоит уточнить, что именно понимают под словом "корень".
Зачем? В оригинале речь идет об "общей части слов". Слово "корень" звучит во второй задаче, но, мне кажется, исключительно для упрощения лексики..

> полдня пытаюсь угадать, на каком тесте моя программка не работает.
У тебя есть программка? Почему бы не показать?..

> где-то сказано, что наложения быть не может?
Нет, не сказано. Беру слова обратно

> противоречие... чему противоречит-то?
Да, противоречит условию. Если есть чередование гласных (прошу прощение за употребление специального термина из другой области, не из программирования), то части слов не могут считаться общими в принятых рамках.

> вырожденный, но это не значит недопустимый...
Конечно. Просто неинтересный. И моя программа с ним прекрасно справляется..

> ждем автора
С нетерпением..

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

[Patam]

Эээмм..
По сложности 2-я задача равна 1-ой, так что не надо учитывать чередования и прочее.

[мисс_граффити]

> стоит уточнить, что именно понимают под словом "корень".
Зачем? В оригинале речь идет об "общей части слов". Слово "корень" звучит во второй задаче, но, мне кажется, исключительно для упрощения лексики..

Вот именно. В первой - об общей части слов, во второй - о корне. "Это жжж неспроста" (с)

> полдня пытаюсь угадать, на каком тесте моя программка не работает.
У тебя есть программка? Почему бы не показать?..

Это про шарик и нитку... я про нее писала, никто не заинтересовался.

> противоречие... чему противоречит-то?
Да, противоречит условию. Если есть чередование гласных (прошу прощение за употребление специального термина из другой области, не из программирования), то части слов не могут считаться общими в принятых рамках.

я первую задачу вообще не трогаю... только про вторую говорю.

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

я о том же.