original_docstring: r"""
          Return a longest subword of ``self`` and ``other``.
  
          A subword of a word is a subset of the word's letters, read in the
          order in which they appear in the word.
  
          For more information, see
          :wikipedia:`Longest_common_subsequence_problem`.
  
          INPUT:
  
          - ``other`` -- a word
  
          ALGORITHM:
  
          For any indices `i,j`, we compute the longest common subword ``lcs[i,j]`` of
          ``self[:i]`` and ``other[:j]``. This can be easily obtained as the longest
          of
  
          - ``lcs[i-1,j]``
  
          - ``lcs[i,j-1]``
  
          - ``lcs[i-1,j-1]+self[i]`` if ``self[i]==other[j]``
  
          EXAMPLES::
  
              sage: v1 = Word("abc")
              sage: v2 = Word("ace")
              sage: v1.longest_common_subword(v2)
              word: ac
  
              sage: w1 = Word("1010101010101010101010101010101010101010")
              sage: w2 = Word("0011001100110011001100110011001100110011")
              sage: w1.longest_common_subword(w2)
              word: 00110011001100110011010101010
  
          TESTS::
  
              sage: Word().longest_common_subword(Word())
              word:
  
          .. SEEALSO::
  
              :meth:`is_subword_of`
          
docstring: 
  
  A subword of a word is a subset of the word's letters, read in the
  order in which they appear in the word.
  
  For more information, see
docstring_tokens: A subword of a word is a subset of the word ' s letters read in the order in which they appear in the word . For more information see
code: def longest_common_subword(self, other):
          r"""
          Return a longest subword of ``self`` and ``other``.
  
          A subword of a word is a subset of the word's letters, read in the
          order in which they appear in the word.
  
          For more information, see
          :wikipedia:`Longest_common_subsequence_problem`.
  
          INPUT:
  
          - ``other`` -- a word
  
          ALGORITHM:
  
          For any indices `i,j`, we compute the longest common subword ``lcs[i,j]`` of
          ``self[:i]`` and ``other[:j]``. This can be easily obtained as the longest
          of
  
          - ``lcs[i-1,j]``
  
          - ``lcs[i,j-1]``
  
          - ``lcs[i-1,j-1]+self[i]`` if ``self[i]==other[j]``
  
          EXAMPLES::
  
              sage: v1 = Word("abc")
              sage: v2 = Word("ace")
              sage: v1.longest_common_subword(v2)
              word: ac
  
              sage: w1 = Word("1010101010101010101010101010101010101010")
              sage: w2 = Word("0011001100110011001100110011001100110011")
              sage: w1.longest_common_subword(w2)
              word: 00110011001100110011010101010
  
          TESTS::
  
              sage: Word().longest_common_subword(Word())
              word:
  
          .. SEEALSO::
  
              :meth:`is_subword_of`
          """
          from sage.combinat.words.word import Word
          if len(self) == 0 or len(other) == 0:
              return Word()
  
          w2 = list(other)
  
          # In order to avoid storing lcs[i,j] for each pair i,j of indices, we
          # only store the lcs[i,j] for two consecutive values of i. At any step
          # of the algorithm, lcs[i,j] is stored at lcs[0][j] and lcs[i-1,j] is
          # stored at lcs[1][j]
  
          # The weird +1 that follows exists to make sure that lcs[i,-1] returns
          # the empty word.
          lcs = [[[] for i in range(len(w2)+1)] for j in range(2)]
  
          for i,l1 in enumerate(self):
              for j,l2 in enumerate(other):
                  lcs[0][j] = max(lcs[0][j-1], lcs[1][j],
                                  lcs[1][j-1] + ([l1] if l1==l2 else []),key=len)
  
              # Maintaining the meaning of lcs for the next loop
              lcs.pop(1)
              lcs.insert(0,[[] for i in range(len(w2)+1)])
  
          return Word(lcs[1][-2])
code_tokens: def longest_common_subword ( self , other ) : from sage . combinat . words . word import Word if len ( self ) == 0 or len ( other ) == 0 : return Word ( ) w2 = list ( other ) lcs = [ [ [ ] for i in range ( len ( w2 ) + 1 ) ] for j in range ( 2 ) ] for i , l1 in enumerate ( self ) : for j , l2 in enumerate ( other ) : lcs [ 0 ] [ j ] = max ( lcs [ 0 ] [ j - 1 ] , lcs [ 1 ] [ j ] , lcs [ 1 ] [ j - 1 ] + ( [ l1 ] if l1 == l2 else [ ] ) , key = len ) lcs . pop ( 1 ) lcs . insert ( 0 , [ [ ] for i in range ( len ( w2 ) + 1 ) ] ) return Word ( lcs [ 1 ] [ - 2 ] )
short_docstring: r"""
  Return a longest subword of ``self`` and ``other``.
short_docstring_tokens: r " " " Return a longest subword of ` ` self ` ` and ` ` other ` ` .
comment: r"""
          Return a longest subword of ``self`` and ``other``.
  
          A subword of a word is a subset of the word's letters, read in the
          order in which they appear in the word.
  
          For more information, see
          :wikipedia:`Longest_common_subsequence_problem`.
  
          INPUT:
  
          - ``other`` -- a word
  
          ALGORITHM:
  
          For any indices `i,j`, we compute the longest common subword ``lcs[i,j]`` of
          ``self[:i]`` and ``other[:j]``. This can be easily obtained as the longest
          of
  
          - ``lcs[i-1,j]``
  
          - ``lcs[i,j-1]``
  
          - ``lcs[i-1,j-1]+self[i]`` if ``self[i]==other[j]``
  
          EXAMPLES::
  
              sage: v1 = Word("abc")
              sage: v2 = Word("ace")
              sage: v1.longest_common_subword(v2)
              word: ac
  
              sage: w1 = Word("1010101010101010101010101010101010101010")
              sage: w2 = Word("0011001100110011001100110011001100110011")
              sage: w1.longest_common_subword(w2)
              word: 00110011001100110011010101010
  
          TESTS::
  
              sage: Word().longest_common_subword(Word())
              word:
  
          .. SEEALSO::
  
              :meth:`is_subword_of`
          """$SEP$# In order to avoid storing lcs[i,j] for each pair i,j of indices, we$SEP$# only store the lcs[i,j] for two consecutive values of i. At any step$SEP$# of the algorithm, lcs[i,j] is stored at lcs[0][j] and lcs[i-1,j] is$SEP$# stored at lcs[1][j]$SEP$# The weird +1 that follows exists to make sure that lcs[i,-1] returns$SEP$# the empty word.$SEP$# Maintaining the meaning of lcs for the next loop