Lua

local string = require "string"
local table = require "table"

local byte = string.byte
local char = string.char
local unpack = table.unpack

pt = os.clock()
print('prepare')

-- somewhere from stackoverflow.com

function trim_spaces (str)
  if str == '' then
    return str
  else
    local startPos = 1
    local endPos   = #str

    while (startPos < endPos and str:byte(startPos) <= 32) do
      startPos = startPos + 1
    end

    if startPos >= endPos then
      return ''
    else
      while (endPos > 0 and str:byte(endPos) <= 32) do
        endPos = endPos - 1
      end

      return str:sub(startPos, endPos)
    end
  end
end -- .function trim

-- from https://github.com/nmap/nmap/blob/master/nselib/unicode.lua

function utf8_enc(cp)
  local bytes = {}
  local n, mask

  if cp % 1.0 ~= 0.0 or cp < 0 then
    -- Only defined for nonnegative integers.
    return nil
  elseif cp <= 0x7F then
    -- Special case of one-byte encoding.
    return char(cp)
  elseif cp <= 0x7FF then
    n = 2
    mask = 0xC0
  elseif cp <= 0xFFFF then
    n = 3
    mask = 0xE0
  elseif cp <= 0x10FFFF then
    n = 4
    mask = 0xF0
  else
    return nil
  end

  while n > 1 do
    bytes[n] = char(0x80 + (cp & 0x3F))
    cp = cp >> 6
    n = n - 1
  end
  bytes[1] = char(mask + cp)

  return table.concat(bytes)
end

function utf8_dec(buf, pos)
  pos = pos or 1
  local n, mask
  local bv = byte(buf, pos)
  if bv <= 0x7F then
    return pos+1, bv
  elseif bv <= 0xDF then
    --110xxxxx 10xxxxxx
    n = 1
    mask = 0xC0
  elseif bv <= 0xEF then
    --1110xxxx 10xxxxxx 10xxxxxx
    n = 2
    mask = 0xE0
  elseif bv <= 0xF7 then
    --11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
    n = 3
    mask = 0xF0
  else
    return nil, string.format("Invalid UTF-8 byte at %d", pos)
  end

  local cp = bv - mask

  if pos + n > #buf then
    return nil, string.format("Incomplete UTF-8 sequence at %d", pos)
  end
  for i = 1, n do
    bv = byte(buf, pos + i)
    if bv < 0x80 or bv > 0xBF then
      return nil, string.format("Invalid UTF-8 sequence at %d", pos + i)
    end
    cp = (cp << 6) + (bv & 0x3F)
  end

  return pos + 1 + n, cp
end

function decode(buf, decoder, bigendian)
  local cp = {}
  local pos = 1
  while pos <= #buf do
    pos, cp[#cp+1] = decoder(buf, pos, bigendian)
  end
  return cp
end

function encode(list, encoder, bigendian)
  local buf = {}
  for i, cp in ipairs(list) do
    buf[i] = encoder(cp, bigendian)
  end
  return table.concat(buf, "")
end

-- somewhere from stackoverflow.com

-- see if the file exists
function file_exists(file)
  local f = io.open(file, "rb")
  if f then f:close() end
  return f ~= nil
end

-- get all lines from a file, returns an empty
-- list/table if the file does not exist
function lines_from(file)
  if not file_exists(file) then return {} end
  lines = {}
  for line in io.lines(file) do
    lines[#lines + 1] = decode(trim_spaces(line), utf8_dec)
  end
  return lines
end

-- tests the functions above
local file = '../../russian_nouns.txt'
local lines = lines_from(file)

-- -- print all line numbers and their contents
-- for k,v in pairs(lines) do
--   print('line[' .. k .. ']', v)
-- end

-- own

local found = ''
local fln = 1
local hti = ''
local xln = 1

function ps(x)
  return encode(x, utf8_enc)
end

function get_intersection(ar, br, fln)

  local i = 1

  for j = 2, #ar do

    if i == #br then
      break
    end

    local r = ar[j]

    if br[i] == r then
        i = i + 1
    else
        i = 1
    end

  end

  if (i <= fln) or (i >= #ar) or (i >= #br) then
    return '', 1
  end

  -- print('[8] I ' .. i)
  return ps({ unpack(ar, 1, #ar - i + 1) }) ..
     '[' ..
     ps({ unpack(ar, #ar - i + 2, #ar) }) ..
     ']' ..
     ps({ unpack(br, i, #br) }), i
end

print('prepared after ' .. os.clock() - pt .. 's')
print()
print('start')
sp = os.clock()

for i, f in pairs(lines) do
  for j, x in pairs(lines) do
    if i == j then
        goto continue -- skip the same
    end

    if fln > 1 and ((#f <= (fln+2)) or (#x <= (fln+2))) then
        goto continue -- looking for a longer
    end

        hti, xln = get_intersection(f, x, fln)
        if xln > 1 then
           found, fln = hti, xln
           print(fln-1, found)
        end

    ::continue::
  end
end

print()
print(fln-1, found, 'after ' .. os.clock() - sp .. 's')