Во-первых, вы должны найти все вхождения начальной и конечной строк в ваших шаблонах.Затем вам нужно выяснить, какие теги подходят друг другу (они не подходят, если конечная строка находится перед начальной строкой или находится в той же позиции и, следовательно, касается).затем вы можете сгенерировать ваши теги и вставить в вашу строку вывода.обратите внимание, что вам нужно добавить количество вставленных символов в ваши позиции, потому что длина строки меняется при вставке тегов.Кроме того, вы должны отсортировать теги по позициям перед их вставкой, иначе было бы очень сложно вычислить, как далеко вы должны сдвинуть позиции.Вот короткий пример на Ruby:
patterns = [['CAT','TREE'], ['LION','FOREST'], ['OWL','WATERFALL']]
strings = ['THEREISACATINTHETREE.', 'THETREEHASACAT.', 'THECATTREEHASMANYBIRDS.', 'THECATANDLIONLEFTTHEFORESTANDMETANDOWLINTREENEARTHEWATERFALL.', 'THECATDOESNOTLIKETALLTREES,BUTINSTEADLIKESSHORTTREES.', 'ACATONATREEANDANOTHERCATONANOTHERTREE.', 'ACATONATREEBUTNOCATTREE.']
strings.each do |string|
matches = {}; tags = []
counter = shift = 0
output = string.dup
patterns.each do |sstr,estr| # loop through all patterns
posa = []; posb = []; #
string.scan(sstr){posa << $~.end(0)} # remember found positions and
string.scan(estr){posb << $~.begin(0)} # find all valid combinations (next line)
matches[[sstr,estr]] = posa.product(posb).reject{|s,e|s>=e}
end
matches.each do |pat,pos| # loop through all matches
pos.each do |s,e| #
tags << [s,"\\start{#{counter += 1}}"] # generate and remember \start{}
tags << [e,"\\end{#{counter}}"] # and \end{} tags
end
end
tags.sort.each do |pos,tag| # sort and loop through tags
output.insert(pos+shift,tag) # insert tag and increment
shift += tag.chars.count # shift by num. of inserted chars
end
puts string, output # print result
end
Это не красиво, но оно отвечает всем вашим требованиям.Следующий пример, я думаю, немного более читабелен и пригоден для повторного использования, и он реализован как класс Ruby с соответствующими модульными тестами, чтобы гарантировать его работу:
class PatternMarker
require 'english'
attr_reader :input, :output, :matches
def initialize patterns
@patterns = patterns
raise ArgumentError, 'no patterns given' unless @patterns.any?
@patterns.each do |p|
raise ArgumentError, 'every pattern must have exactly two strings' unless p.count == 2
end
end
def parse input
@input = input.dup
match_patterns
generate_output
self
end
def match?
@matches.any?
end
private
def match_patterns
@matches = {}
@patterns.each do |start_str,end_str|
pos = { :start => [], :end => [] }
@input.scan(start_str){ pos[:start] << $LAST_MATCH_INFO.end(0) }
@input.scan(end_str ){ pos[:end] << $LAST_MATCH_INFO.begin(0) }
@matches[[start_str,end_str]] = pos[:start].product(pos[:end])
@matches[[start_str,end_str]].reject!{ |s,e| e <= s }
@matches.reject!{ |p,pos| pos.none? }
end
end
def generate_output
tags = []
counter = shift = 0
@output = @input.dup
@matches.each do |pattern,positions|
positions.each do |s,e|
counter += 1
tags << [s, "\\start{#{counter}}"]
tags << [e, "\\end{#{counter}}" ]
end
end
tags.sort!.each do |position,tag|
@output.insert(position+shift,tag)
shift += tag.chars.count
end
end
end
в действии:
patterns = [
['CAT' , 'TREE' ],
['LION', 'FOREST' ],
['OWL' , 'WATERFALL']
]
strings = [
'THEREISACATINTHETREE.',
'THETREEHASACAT.',
'THECATTREEHASMANYBIRDS.',
'THECATANDLIONLEFTTHEFORESTANDMETANDOWLINTREENEARTHEWATERFALL.',
'THECATDOESNOTLIKETALLTREES,BUTINSTEADLIKESSHORTTREES.',
'ACATONATREEANDANOTHERCATONANOTHERTREE.',
'ACATONATREEBUTNOCATTREE.'
]
marker = PatternMarker.new(patterns)
strings.each do |string|
marker.parse(string)
puts "input: #{marker.input}"
if marker.match?
puts "output: #{marker.output}"
else
puts "(does not match)"
end
puts
end
вывод:
input: THEREISACATINTHETREE.
output: THEREISACAT\start{1}INTHE\end{1}TREE.
input: THETREEHASACAT.
(does not match)
input: THECATTREEHASMANYBIRDS.
(does not match)
input: THECATANDLIONLEFTTHEFORESTANDMETANDOWLINTREENEARTHEWATERFALL.
output: THECAT\start{1}ANDLION\start{2}LEFTTHE\end{2}FORESTANDMETANDOWL\start{3}IN\end{1}TREENEARTHE\end{3}WATERFALL.
input: THECATDOESNOTLIKETALLTREES,BUTINSTEADLIKESSHORTTREES.
output: THECAT\start{1}\start{2}DOESNOTLIKETALL\end{1}TREES,BUTINSTEADLIKESSHORT\end{2}TREES.
input: ACATONATREEANDANOTHERCATONANOTHERTREE.
output: ACAT\start{1}\start{2}ONA\end{1}TREEANDANOTHERCAT\start{3}ONANOTHER\end{2}\end{3}TREE.
input: ACATONATREEBUTNOCATTREE.
output: ACAT\start{1}\start{2}ONA\end{1}TREEBUTNOCAT\end{2}TREE.
тесты:
require 'test/unit'
class TestPatternMarker < Test::Unit::TestCase
def setup
@patterns = [
['CAT' , 'TREE' ],
['LION', 'FOREST' ],
['OWL' , 'WATERFALL']
]
@marker = PatternMarker.new(@patterns)
end
def test_should_parse_simple
@marker.parse 'THEREISACATINTHETREE.'
assert @marker.match?
assert_equal 'THEREISACAT\start{1}INTHE\end{1}TREE.', @marker.output
end
def test_should_parse_reverse
@marker.parse 'THETREEHASACAT.'
assert !@marker.match?
assert_equal @marker.input, @marker.output
end
def test_should_parse_touching
@marker.parse 'THECATTREEHASMANYBIRDS.'
assert !@marker.match?
assert_equal @marker.input, @marker.output
end
def test_should_parse_multiple_patterns
@marker.parse 'THECATANDLIONLEFTTHEFORESTANDMETANDOWLINATREENEARTHEWATERFALL.'
assert @marker.match?
assert_equal 'THECAT\start{1}ANDLION\start{2}LEFTTHE\end{2}FORESTANDMETANDOWL\start{3}INA\end{1}TREENEARTHE\end{3}WATERFALL.', @marker.output
end
def test_should_mark_multiple_matches_at_same_place
@marker.parse 'THECATDOESNOTLIKETALLTREES,BUTINSTEADLIKESSHORTTREES.'
assert @marker.match?
assert_equal 'THECAT\start{1}\start{2}DOESNOTLIKETALL\end{1}TREES,BUTINSTEADLIKESSHORT\end{2}TREES.', @marker.output
end
def test_should_mark_all_possible_matches
@marker.parse 'CATFOOTREEFOOCATFOOTREE.'
assert @marker.match?
assert_equal 'CAT\start{1}\start{2}FOO\end{1}TREEFOOCAT\start{3}FOO\end{2}\end{3}TREE.', @marker.output
end
def test_should_accept_input
@marker.parse 'CATINTREE'
assert @marker.match?
assert_equal 'CATINTREE', @marker.input
@marker.parse 'FOOBAR'
assert !@marker.match?
assert_equal 'FOOBAR', @marker.input
end
def test_should_only_accept_valid_patterns
assert_raise ArgumentError do PatternMarker.new([]) end
assert_raise ArgumentError do PatternMarker.new(['FOO','BAR']) end
assert_raise ArgumentError do PatternMarker.new(['FOO','BAR'],['FOO','BAR','BAZ']) end
assert_raise ArgumentError do PatternMarker.new(['FOO','BAR'],['BAZ']) end
assert_nothing_raised do PatternMarker.new([['FOO','BAR']]) end
end
end
тестовый вывод:
Loaded suite pattern
Started
........
Finished in 0.003910 seconds.
8 tests, 21 assertions, 0 failures, 0 errors, 0 skips
Test run options: --seed 31173
редактирование: добавлены тесты и упрощены некоторые коды