Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм подсветки совпадений в двух строках / 25 сообщений из 26, страница 1 из 2
18.09.2009, 19:29:26
    #36205187
Igor Vitaliev
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Есть две строки. Нужно найти в них совпадающие подстроки. Например:
какаятострокалевоготекста
непонятночтозатекстоваястрока

Как такую штуку сделать?
...
Рейтинг: 0 / 0
18.09.2009, 20:03:34
    #36205232
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
без введения минимальной длины совпадающей подстроки задача неполна.

Модератор:
редактировано
...
Рейтинг: 0 / 0
18.09.2009, 20:38:07
    #36205265
Igor Vitaliev
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Не понял... может имелось ввиду "минимальной длины совпадающей подстроки"? Если так, то пусть будет, например, 3. Если не так, то тогда прошу объяснить подробнее.
...
Рейтинг: 0 / 0
18.09.2009, 21:11:35
    #36205289
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Igor VitalievНе понял... может имелось ввиду "минимальной длины совпадающей подстроки"? Если так, то пусть будет, например, 3. Если не так, то тогда прошу объяснить подробнее.Да, именно так. Прошу прощения за свое косноязычие.
...
Рейтинг: 0 / 0
19.09.2009, 00:53:35
    #36205472
crt
crt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
чем-то мне это архивирование напоминает.
там ведь тоже совпадающие подстроки ищут, насколько я понимаю
...
Рейтинг: 0 / 0
19.09.2009, 01:07:05
    #36205479
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
miksoft,

а зачем? И почему не полна
...
Рейтинг: 0 / 0
19.09.2009, 11:06:49
    #36205558
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
tchingizmiksoft,

а зачем? И почему не полнаа потому что иначе один символ - это тоже подстрока.
и для более-менее длинных исходных строк практически всё будет совпадать.

два символа - тоже очень часто могут совпадать.
в приведенном примере должны совпадать подстроки "ка", "ят", "то"...
...
Рейтинг: 0 / 0
19.09.2009, 11:58:32
    #36205580
Аналитик88
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Если знаете, ответьте для случая где длина совпадающей строки задается переменной.
...
Рейтинг: 0 / 0
19.09.2009, 12:00:04
    #36205581
Аналитик88
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Или возможно задать поиск полностью совпадающих слов, т е окруженных проблема.
...
Рейтинг: 0 / 0
19.09.2009, 13:42:34
    #36205633
SQL_Lamer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Вот готовый код для поиска и замены подстрок в текстовом файле.
Из книги "Ansi Common Lisp"
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
(defstruct buf
  vec (start - 1 ) (used - 1 ) (new - 1 ) (end - 1 ))

(defun bref (buf n)
  (svref (buf-vec buf)
         (mod n (length (buf-vec buf)))))

(defun (setf bref) (val buf n)
  (setf (svref (buf-vec buf)
               (mod n (length (buf-vec buf))))
        val))

(defun new-buf (len)
  (make-buf :vec (make-array len)))

(defun buf-insert (x b)
  (setf (bref b (incf (buf-end b))) x))

(defun buf-pop (b)
  (prog1
      (bref b (incf (buf-start b)))
    (setf (buf-used b) (buf-start b)
          (buf-new b) (buf-end b))))

(defun buf-next (b)
  (when (< (buf-used b) (buf-new b))
    (bref b (incf (buf-used b)))))

(defun buf-reset (b)
  (setf (buf-used b) (buf-start b)
        (buf-new b) (buf-end b)))

(defun buf-clear (b)
  (setf (buf-start b) - 1  (buf-used b) - 1 
        (buf-new b) - 1  (buf-end b) - 1 ))

(defun buf-flush (b str)
  (do ((i ( 1 + (buf-used b)) ( 1 + i)))
      ((> i (buf-end b)))
    (princ (bref b i) str)))

(defun file-subst (old new file1 file2)
  (with-open-file (in file1 :direction :input)
    (with-open-file (out file2 :direction :output
                         :if-exists :supersede)
      (stream-subst old new in out))))


(defun stream-subst (old new in out)
  (let* ((pos  0 )
         (len (length old))
         (buf (new-buf len))
         (from-buf nil))
    (do ((c (read-char in nil :eof)
            (or (setf from-buf (buf-next buf))
                (read-char in nil :eof))))
        ((eql c :eof))
      (cond ((char= c (char old pos))
             (incf pos)
             (cond ((= pos len)             
                    (princ new out)
                    (setf pos  0 )
                    (buf-clear buf))
                   ((not from-buf)         
                    (buf-insert c buf))))
            ((zerop pos)                   
             (princ c out)
             (when from-buf
               (buf-pop buf)
               (buf-reset buf)))
            (t                              
             (unless from-buf
               (buf-insert c buf))
             (princ (buf-pop buf) out)
             (buf-reset buf)
             (setf pos  0 ))))
    (buf-flush buf out))) 


Работает так:

В файле "testl" находится следующий текст:

«The struggle between Liberty and Authority is the most
conspicuous feature in the portions of history with which
we are earliest familiar, particularly in that of Greece,
Rome, and England. »


После вычисления
Код: plaintext
(file-subst " th" " z" "test1" "test2")

, файл "test2" будет содержать:

«The struggle between Liberty and Authority is ze most
conspicuous feature in ze portions of history with which
we are earliest familiar, particularly in zat of Greece,
Rome, and England. »


Пользуйся, если разберешься.
...
Рейтинг: 0 / 0
19.09.2009, 13:52:05
    #36205634
SQL_Lamer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Вот черт. Че то я не в тему. Тебе подсветку надо, а не замену.
Ну, принцип то один :)
Когда находим совпадение, не меняем, а подсвечиваем :)
Главное - найти.
...
Рейтинг: 0 / 0
19.09.2009, 13:57:41
    #36205640
SQL_Lamer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Нет, что то вообще не в тему, смотрю.
Надо меньше пить :(
Чингис, удали меня нафиг из этого топика :)
...
Рейтинг: 0 / 0
19.09.2009, 20:32:31
    #36205863
ResearchStudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Igor VitalievЕсть две строки. Нужно найти в них совпадающие подстроки. Например:
какаятострокалевоготекста
непонятночтозатекстоваястрока

Как такую штуку сделать?

"в лоб" это решается четырьмя вложенными циклами. Какая длина строк ?
...
Рейтинг: 0 / 0
19.09.2009, 20:38:59
    #36205873
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
ResearchStudio"в лоб" это решается четырьмя вложенными циклами. Какая длина строк ?а четвертый зачем?
...
Рейтинг: 0 / 0
19.09.2009, 21:23:45
    #36205916
Igor Vitaliev
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
ResearchStudioКакая длина строк ?
Не сильно длинные, примерно 30-50 символов.
...
Рейтинг: 0 / 0
19.09.2009, 22:11:20
    #36205953
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
кстати, еще нужно задать, учитываются наложения или нет.
например в строках "123кукуку456" и "78куку90" нужно сколько символов в первой строке выделять? 4 или 6?
...
Рейтинг: 0 / 0
19.09.2009, 22:13:06
    #36205956
ResearchStudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
miksoftResearchStudio"в лоб" это решается четырьмя вложенными циклами. Какая длина строк ?а четвертый зачем?

вообще да, можно обойтись тремя
...
Рейтинг: 0 / 0
19.09.2009, 22:15:55
    #36205961
ResearchStudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Igor VitalievResearchStudioКакая длина строк ?
Не сильно длинные, примерно 30-50 символов.

тогда "в лоб" перебирать, проще всего

менее 125 000 итераций для двух строк в 50 символов.
По времени это меньше половины секунды наверное займет
...
Рейтинг: 0 / 0
19.09.2009, 22:18:53
    #36205963
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
ResearchStudioменее 125 000 итераций для двух строк в 50 символов.Хм, по-моему - 2500 итераций в худшем случае (когда нет совпадений).
...
Рейтинг: 0 / 0
19.09.2009, 22:21:02
    #36205968
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
miksoftResearchStudioменее 125 000 итераций для двух строк в 50 символов.Хм, по-моему - 2500 итераций в худшем случае (когда нет совпадений).это если наложения совпадений не допускаются.
...
Рейтинг: 0 / 0
19.09.2009, 22:34:50
    #36205981
ResearchStudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
miksoftmiksoftResearchStudioменее 125 000 итераций для двух строк в 50 символов.Хм, по-моему - 2500 итераций в худшем случае (когда нет совпадений).это если наложения совпадений не допускаются.

больше 2500, однозначно

первый цикл перебирает позицию в первой строке
второй цикл перебирает позицию во второй строке
третий цикл перебирает предпологаемую длину подстроки

тоесть если быть более точным гдето 2500*25
...
Рейтинг: 0 / 0
19.09.2009, 22:36:00
    #36205983
ResearchStudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
но это общие прикиды, суть в том что "в лоб" здесь решение наиболее простое и приемлемое по времени
...
Рейтинг: 0 / 0
21.09.2009, 19:23:39
    #36208572
Igor Vitaliev
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
Да, похоже, что можно делать "в лоб".
...
Рейтинг: 0 / 0
21.09.2009, 19:48:16
    #36208616
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
ResearchStudiomiksoftmiksoftResearchStudioменее 125 000 итераций для двух строк в 50 символов.Хм, по-моему - 2500 итераций в худшем случае (когда нет совпадений).это если наложения совпадений не допускаются.

больше 2500, однозначно

первый цикл перебирает позицию в первой строке
второй цикл перебирает позицию во второй строке
третий цикл перебирает предпологаемую длину подстроки

тоесть если быть более точным гдето 2500*25Если наложения совпадений не допускаются, то третий цикл может продвигать счетчики первого и второго.
...
Рейтинг: 0 / 0
21.09.2009, 21:35:18
    #36208694
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм подсветки совпадений в двух строках
miksofttchingizmiksoft,

а зачем? И почему не полнаа потому что иначе один символ - это тоже подстрока.
и для более-менее длинных исходных строк практически всё будет совпадать.

два символа - тоже очень часто могут совпадать.
в приведенном примере должны совпадать подстроки "ка", "ят", "то"...
и шо? в условии ограничений не было. Может постановщик задач хочет найти
подстроки длиной 1 тоже. Зачем отсебя придумывать?
Я понимаю добавлять ограничения, если не можешь решить.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм подсветки совпадений в двух строках / 25 сообщений из 26, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]