String pattern matching

[forward at seznam.cz]

Firstly sort variable expressions by its length

xy  = 'abca'
xyz = 'abcaaab'
vxw = 'eeabcac'

Expand all expressions by its values except itself

xy       = 'abca'
'abca' z = 'abcaaab'
vxw      = 'eeabcac'

Cut all left and right matches

xy  = 'abca'
z   = 'aab'
vxw = 'eeabcac'

Repeat until you can.

z   = 'aab'
xy  = 'abca'
vxw = 'eeabcac'

Get first variable expression intersection
- variables: x is longest intersection of xy and vxw
- value    : 'abca' starting at position 2 of vxw (longest intersection
of 'abca' and 'eeabcac')
             'a' starting at position 5 of vxw

Then try matching:
x='abca' (at position 2 of vxw)
x='abc'  (at position 2 of vxw)
x='ab'   (at position 2 of vxw)
x='a'	 (at position 2 of vxw)
x='a'	 (at position 5 of vxw)
x=''	 (at position arbitrary position of vxw)
and calculate the others.

Repeat all step until you can.


In your example, there are 13 results.
x='abca' y=''     z='aab' v='ee'      w='c'
x='abc'  y='a'    z='aab' v='ee'      w='ac'
x='ab'   y='ca'   z='aab' v='ee'      w='cac'
x='a'    y='bca'  z='aab' v='ee'      w='bcac'
x='a'    y='bca'  z='aab' v='eeabc'   w='c'
x=''     y='abca' z='aab' v=''        w=''
x=''     y='abca' z='aab' v='e'       w='eabcac'
x=''     y='abca' z='aab' v='ee'      w='abcac'
x=''     y='abca' z='aab' v='eea'     w='bcac'
x=''     y='abca' z='aab' v='eeab'    w='cac'
x=''     y='abca' z='aab' v='eeabc'   w='ac'
x=''     y='abca' z='aab' v='eeabca'  w='c'
x=''     y='abca' z='aab' v='eeabcac' w=''

with the same original expressions

xy  = 'abca'
xyz = 'abcaaab'
vxw = 'eeabcac'

Note that maximum matching is best matching in some kind of problems.

Cutting off empty values, you can get 4 results:
x='abc'  y='a'    z='aab' v='ee'      w='ac'
x='ab'   y='ca'   z='aab' v='ee'      w='cac'
x='a'    y='bca'  z='aab' v='ee'      w='bcac'
x='a'    y='bca'  z='aab' v='eeabc'   w='c'