Problem:


 共通部分文字列   

問題

  2 個の文字列が与えられたとき, 両方の文字列に含まれる文字列のうち最も長いものを探し, その長さを答えるプログラムを作成せよ.

  ここで, 文字列 s が文字列 t に含まれるとは, t の中に s が連続して現れることをいう. 空文字列, すなわち長さ 0 の文字列は, どんな文字列にも含まれる. 例えば, 文字列 ABRACADABRA には次の文字列が含まれる: ABRA, RAC, D, ACADABRA, ABRACADABRA,空文字列など. 一方, 文字列 ABRACADABRA には次の文字列は含まれない: ABRC, RAA,BA, K など.

例

 例 1: 文字列として ABRACADABRA と ECADADABRBCRDARA が与えられた場合, 両方に含まれる文字列には CA や CADA や ADABR や空文字列などがある. そのうち最も長いのは ADABR であり, その長さは 5 である. 2 個の文字列の中に含まれる ADABR
の位置を以下に示す.

ABRACADABRA

ECADADABRBCRDARA

 例 2: 文字列として UPWJCIRUCAXIIRGL と SBQNYBSBZDFNEV が与えられた場合, 両方に含まれる文字列は空文字列のみであり, その長さは 0 である.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

 入力は 2 行からなり, 1 行目に 1 個目の文字列が, 2 行目に 2 個目の文字列が与えられる. 文字列は英大文字からなり, 各々の文字列の長さは 1 以上 4000 以下である.

 採点用データのうち, 配点の 30% 分については, 各々の文字列の長さは 1 以上 50以下である.

入力の終わりは EOF で示される. データセットの数は 10 を超えない．

出力

データセットごとに与えられた 2 個の文字列の両方に含まれる文字列のうち最も長いものの長さを 1 行に出力する.

入出力例

入力例

ABRACADABRA
ECADADABRBCRDARA
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

出力例

5
0

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
ABRACADABRA
ECADADABRBCRDARA
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV


Sample output:
5
0

Submission status: Wrong Answer

Solution code:
import difflib

while True:
    try:
        a, b = input().strip(), input().strip()
    except:
        break
    sm = difflib.SequenceMatcher(a=a, b=b)
    print(sm.find_longest_match(0, len(a), 0, len(b)).size)

Submission status: Wrong Answer

Solution code:
s1 = input()
s2 = input()
ordA = ord("a")
mod1 = 1000000007
mod2 = 2147483647

def r_hash(s):
  length = len(s)
  h_lst = [0] * length
  acc1 = acc2 = 0
  for i in range(length):
    acc1 = (acc1 * 26 + ord(s[i]) - ordA) % mod1
    acc2 = (acc2 * 26 + ord(s[i]) - ordA) % mod2
    h_lst[i] = (acc1, acc2)
  return h_lst

h_s1 = r_hash(s1)
h_s2 = r_hash(s2)

def search(length):
  hl_s1 = set()
  base1 = 26 ** length % mod1
  base2 = 26 ** length % mod2
  for i in range(len(s1) - length):
    hl_s1.add((h_s1[i + length][0] - h_s1[i][0] * base1,
               h_s1[i + length][1] - h_s1[i][1] * base2))

  for i in range(len(s2) - length):
    if (h_s2[i + length][0] - h_s2[i][0] * base1,
        h_s2[i + length][1] - h_s2[i][1] * base2) in hl_s1:
        return True
  else:
    return False

max_len = min(len(s1), len(s2))
for length in range(max_len, -1, -1):
  if search(length):
    print(length)
    break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			for L in range(ans,len(t)-sp):
				if t[sp:sp+L] in s:
					ans = max(ans,L)
				else:
					break
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			for L in range(ans,len(t)-sp):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			if len(t) - sp <= ans:
				break
			for L in range(ans,len(t)-sp):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		MAXL = sum(min(s.count(i),t.count(i)) for i in set(list(s))&set(list(t)))
		ans = 0
		L = MAXL/2
		for sp in range(len(t)-L+1):
			if t[sp:sp+L] in s:
				ans = L
				L += L/2
				break
		else:
			L -= L/2
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		MAXL = sum(min(s.count(i),t.count(i)) for i in set(list(s))&set(list(t)))
		ans = 0
		L = (MAXL+1)/2
		for sp in range(len(t)-L+1):
			if t[sp:sp+L] in s:
				ans = L
				L += (L+1)/2
				break
		else:
			L -= L/2
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		MAXL = sum(min(s.count(i),t.count(i)) for i in set(list(s))&set(list(t)))
		ans = 0
		L = (MAXL+1)/2
		for sp in range(len(t)-L+1):
			if t[sp:sp+L] in s:
				ans = max(ans,L)
				L += (L+1)/2
				break
		else:
			L -= L/2
		print ans
	except:
		break

Submission status: Time Limit Exceeded

Solution code:
while(1):
    try:
        word1=raw_input()
        word2=raw_input()
    except:
        break
    nmax=0
    headindex=0
    while headindex+nmax+1<len(word1):
        while word1[headindex:headindex+nmax+1] in word2:
            nmax=nmax+1
        headindex=headindex+1
    print nmax

Submission status: Time Limit Exceeded

Solution code:
while(1):
    try:
        word1=raw_input()
        word2=raw_input()
    except:
        break
    nmax=0
    headindex=0
    while headindex+nmax+1<len(word1):
        if word1[headindex:headindex+nmax+1] in word2:
            word2indexes=[]
            word2hi=0
            while(1):
                try:
                    w2inew=word2[word2hi:].index(word1[headindex:headindex+nmax+1])
                    word2indexes.append(word2hi+w2inew)
                    word2hi=word2hi+w2inew+1
                except:
                    break
            for w2headindex in word2indexes:
                while word1[headindex:headindex+nmax+1]==word2[w2headindex:w2headindex+nmax+1]:
                    nmax=nmax+1
        headindex=headindex+1
    print nmax

Submission status: Time Limit Exceeded

Solution code:
while 1:
    try:
        s1 = raw_input()
    except: break
    s2 = raw_input()
    l = len(s1)
    f = False
    for i in range(l,0,-1):
        for j in range(0,l-i+1):
            if j+i > l: break
            x = s2.find(s1[j:j+i])
            if x != -1:
                f = True
                print i
                break
        if f: break
    if i == 1 and not f: print 0

Submission status: Time Limit Exceeded

Solution code:
while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        l = len(s1)
        f = False
        for i in range(l,0,-1):
            for j in range(0,l-i+1):
                if j+i > l: break
                x = s2.find(s1[j:j+i])
                if x != -1:
                    f = True
                    print i
                    break
            if f: break
        if i == 1 and not f: print 0
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        if len(s1) < len(s2): s1,s2 = s2,s1
        l = sum(min(s1.count(i), s2.count(i)) for i in set(list(s1)) & set(list(s2)))
        f = False
        for i in range(l,0,-1):
            for j in range(0,l-i+1):
                x = s2.find(s1[j:j+i])
                if x != -1:
                    f = True
                    print i
                    break
            if f: break
        if i == 1 and not f: print 0
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        if len(s1) < len(s2): s1,s2 = s2,s1
        l = sum(min(s1.count(i), s2.count(i)) for i in set(list(s1)) & set(list(s2)))
        if l == 0: print 0; continue
        f = False
        for i in range(l,0,-1):
            for j in range(len(s2)-i+1):
                if s2[j:j+i] in s1:
                    f = True
                    print i
                    break
            if f: break
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
import difflib

while True:
    try:
        a, b = input().strip(), input().strip()
    except:
        break
    sm = difflib.SequenceMatcher(a=a, b=b, autojunk=False)
    print(sm.find_longest_match(0, len(a), 0, len(b)).size)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        a, b = input().strip(), input().strip()
    except:
        break
    n, m = len(a), len(b)
    dp = [0] * m
    tmp_max = 0
    for i, ca in enumerate(a):
        np = [0] * m
        for j, cb in enumerate(b):
            if ca == cb:
                np[j] = dp[j - 1] + 1 if j else 1
        tmp_max = max(tmp_max, max(np))
        dp = np
    print(tmp_max)

Submission status: Time Limit Exceeded

Solution code:
while True:
    stra = input()
    strb = input()
    n = len(stra)
    m = len(strb)
    mapp = [[0]*(m+1) for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            if stra[i] == strb[j]:
                mapp[i+1][j+1] = mapp[i][j] + 1

    ans = 0
    for i in range(n):
        ans = max(ans,max(mapp[i]))

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Tree:
    def __init__(self):
        self._root = {}
        self._tmp = None

    def add(self, segment):
        node = self._root
        tmp = 0
        for s in segment:
            key = s
            if not key in node:
                node[key] = {}
            node = node[key]
            tmp += 1
        node["total"] = tmp

    def match(self, _input):
        res = self._match(_input, self._root)
        return res

    def _match(self, segment, root):
        if len(segment) == 0:
            self._tmp = root.get("total", 0)
            return self._tmp

        first, rest = segment[0], segment[1:]
        if first in root:
            self._tmp = self._match(rest, root[first])
            if self._tmp is not None:
                return self._tmp
        return 0

while True:
    try:
        a = input()
        b = input()
    except:
        break
    t = Tree()
    candidates = deque([0])
    segments = [a[i:] for i in range(len(a))]
    ngs_a = deque()
    for a in segments:
        while len(a) > 0:
            if a not in ngs_a:
                t.add(a)
                ngs_a.append(a)
            a = a[:-1]
    segments = [b[i:] for i in range(len(b))]
    for b in segments:
        while len(b) > 0:
            tmp = t.match(b)
            if tmp:
                candidates.append(tmp)
            b = b[:-1]
    print(max(set(candidates)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

while True:
    a = input()
    if a == "EOF":
        break
    else:
        z = input()

    if len(a) > len(z):
        b = a
        a = z
    else:
        b = z

    ans = 0
    flg = 0
    for i in range(len(a) + 1, 0, -1):
        if flg == 1:
            break
        num = len(a) + 1 - i
        if num > len(a):
            break
        for ii in range(num):
            target = a[ii: i + ii]
            if target in b:
                ans = len(target)
                flg = 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

while True:
    try:
        a = input()
        z = input()
    except EOFError:
        break

    if len(a) > len(z):
        b = a
        a = z
    else:
        b = z

    ans = 0
    flg = 0
    for i in range(len(a) + 1, 0, -1):
        if flg == 1:
            break
        num = len(a) + 1 - i
        if num > len(a):
            break
        for ii in range(num):
            target = a[ii: i + ii]
            if target in b:
                ans = len(target)
                flg = 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

while 1:
    try:
        a = input()
    except:
        break
    z = input()
    
    if len(a) > len(z):
        b = a
        a = z
    else:
        b = z

    ans = 0
    flg = 0
    for i in range(len(a) + 1, 0, -1):
        if flg == 1:
            break
        num = len(a) + 1 - i
        if num > len(a):
            break
        for ii in range(num):
            target = a[ii: i + ii]
            if target in b:
                ans = len(target)
                flg = 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

while 1:
    try:
        a = input()
    except:
        break
    z = input()

    if len(a) > len(z):
        b = a
        a = z
    else:
        b = z

    ans = 0
    flg = 0
    for i in range(len(a) + 1, 0, -1):
        if flg == 1:
            break
        num = len(a) + 1 - i
        if num > len(a):
            break
        for ii in range(num):
            target = a[ii: i + ii]
            if target in b:
                ans = len(target)
                flg = 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
  try:
    s1 = input()
    s2 = input()
    lst = [[1 if s1[i] == s2[j] else 0 for i in range(len(s1))] for j in range(len(s2))]
    ans = 0
    def search(x,y,count):
      while  x < len(s2) and y < len(s1) and lst[x][y]:
        count += 1
        lst[x][y] = 0
        x += 1
        y += 1
      return count
    for i in range(len(s2)):
      for j in range(len(s1)):
        if lst[i][j]:
          ans = max(ans,search(i,j,0))
    print(ans)
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      lst = [[1 if s1[i] == s2[j] else 0 for i in range(len(s1))] for j in range(len(s2))]
      ans = 0
      def search(x,y,count):
        while  x < len(s2) and y < len(s1) and lst[x][y]:
          count += 1
          lst[x][y] = 0
          x += 1
          y += 1
        return count
      for i in range(len(s2)):
        for j in range(len(s1)):
          if lst[i][j]:
            ans = max(ans,search(i,j,0))
      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      ans = 0
      def search(x,y,count):
        while  x < len(s1) and y < len(s2) and s1[x] == s2[y]:
          count += 1
          x += 1
          y += 1
        return count

      for i in range(len(s1)):
        for j in range(len(s2)):
          if s1[i] == s2[j]:
            ans = max(ans,search(i,j,0))
      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
def search(x,y,s1,s2,end1,end2):
  count = 0
  while  x < end1 and y < end2 and s1[x] == s2[y]:
    count += 1
    x += 1
    y += 1
  return count

def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      ans = 0
      for i in range(end1):
        for j in range(end2):
          if s1[i] == s2[j]:
            a = search(i,j,s1,s2,end1,end2)
            if a > ans:
              ans = a
      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
def search(x,y,s1,s2,end1,end2):
  count = 0
  while  x < end1 and y < end2 and s1[x] == s2[y]:
    count += 1
    x += 1
    y += 1
  return count

def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      dic = dict()
      for i in range(end2):
        alp = s2[i]
        if not alp in dic:
          dic[alp] = [i]
        else:
          dic[alp].append(i)
      ans = 0
      for i in range(end1):
        alp = s1[i]
        if alp in dic:
          for ind in dic[alp]:
            a = search(i, ind, s1, s2, end1, end2)
            if ans < a:
              ans = a
      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      checked = [[False for i in range(end2)] for j in range (end1)]
      dic = {}

      def check(i, j):
        count = 0
        while  i < end1 and j < end2 and (not checked[i][j]) and s1[i] == s2[j]:
          checked[i][j] = True
          i += 1
          j += 1
          count += 1
        return count

      
      for i in range(end2):
        alp = s2[i]
        if alp in dic:
          dic[alp].append(i)
        else:
          dic[alp] = [i]

      ans = 0

      for i in range(end1):
        alp = s1[i]
        if alp in dic:
          lst = dic[alp]
          for j in lst:
            if not checked[i][j]:
              a = check(i, j)
              if a > ans:
                ans = a

      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        s = "." + input()
        t = "." + input()
    except:break
    l = [[0 for _ in range(len(t))] for _ in range(len(s))]
    for i in range(1, len(s)):
        for j in range(1, len(t)):
            if s[i] == t[j]:l[i][j] = l[i - 1][j - 1] + 1
    print(max([max(i) for i in l]))

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      checked = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
      dic = {}

      def check(i, j):
        count = 0
        while not checked[i][j] and i < end1 and j < end2 and s1[i] == s2[j]:
          checked[i][j] = 1
          i += 1
          j += 1
          count += 1
        return count

      
      for i in range(end2):
        alp = s2[i]
        if alp in dic:
          dic[alp].append(i)
        else:
          dic[alp] = [i]

      ans = 0

      for i in range(end1):
        alp = s1[i]
        if alp in dic:
          lst = dic[alp]
          for j in lst:
            if not ((i, j) in checked):
              a = check(i, j)
              if a > ans:
                ans = a

      print(ans)
    except EOFError:
      break
solve()

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s, base, MOD):
        self.s = s
        self.l = l = len(s)
        self.base = base
        self.MOD = MOD
        self.h = h = [0]*(l + 1)
        for i in range(l):
            h[i+1] = (h[i] * base + ord(s[i])) % MOD
    def get(self, l, r):
        MOD = self.MOD
        return ((self.h[r] - self.h[l]*pow(self.base, r-l, MOD) + MOD)) % MOD

C = open(0).read().split()
MOD = 563980774085007485
for t in range(len(C)//2):
    S = C[2*t]; T = C[2*t+1]
    rhs = RollingHash(S, 31, MOD)
    rht = RollingHash(T, 31, MOD)
    L = len(S)
    hs = [set() for i in range(L+1)]
    for l in range(1, L+1):
        hsl = hs[l]
        for i in range(L-l+1):
            hsl.add(rhs.get(i, i+l))
    ans = 0
    M = len(T)
    for l in range(L, 0, -1):
        hsl = hs[l]
        for i in range(M-l+1):
            if rht.get(i, i+l) in hsl:
                break
        else:
            continue
        ans = l
        break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        s = raw_input()
        t = raw_input()
    except:
        break

    ans = 0

    for f in xrange(len(s) + 1):
        s_ = s[f:]
        pr = 0
        for i in xrange(min(len(s_), len(t))):
            if s_[i] == t[i]:
                pr += 1
                ans = max(ans, pr)
            else:
                pr = 0

    for f in xrange(len(t) + 1):
        t_ = t[f:]
        pr = 0
        for i in xrange(min(len(s), len(t_))):
            if s[i] == t_[i]:
                pr += 1
                ans = max(ans, pr)
            else:
                pr = 0

    print ans

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
    n, m = len(s), len(t)

    ans, dp = 0, [0] * (m + 1)
    for i in xrange(n):
        for j in xrange(m, 0, -1):
            if s[i] == t[j - 1]:
                dp[j] = 1 + dp[j - 1]
            else:
                dp[j] = 0
            ans = max(ans, dp[j])
    return ans

while True:
    try:
        s = raw_input().strip()
        t = raw_input().strip()
    except EOFError:
        break

    print solve(s, t)

Submission status: Time Limit Exceeded

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			for L in range(len(t)-sp):
				if t[sp:sp+L] in s:
					ans = max(ans,L)
		print ans
	except:
		break

Submission status: Time Limit Exceeded

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for L in range(len(t),0,-1):
			for sp in range(len(t)-L):
				if t[sp:sp+L] in s:
					ans = L
					break
			if ans > 0:
				break
		print ans
	except:
		break

Submission status: Time Limit Exceeded

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		Ls,Lt = len(s),len(t)
		if Ls < Lt:
			s,t,Ls,Lt = t,s,Lt,Ls
		ans = 0
		for d in range(Lt+1):
			L = 0
			for i in range(d):
				if s[i] == t[-d+i]:
					L += 1
				elif L > 0:
					ans = max(ans,L)
					L = 0
			ans = max(ans,L)
		for d in range(Ls):
			L = 0
			for i in range(min(Lt,Ls-d)):
				if s[i+d] == t[i]:
					L += 1
				elif L > 0:
					ans = max(ans,L)
					L = 0
			ans = max(ans,L)
		print ans
	except:
		break

Submission status: Time Limit Exceeded

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			for L in range(len(t)-sp):
				if t[sp:sp+L] in s:
					ans = max(ans,L)
				else:
					break
		print ans
	except:
		break

Submission status: Memory Limit Exceeded

Solution code:
def solve():
  while True:
    try:
      s1 = input()
      s2 = input()
      end1 = len(s1)
      end2 = len(s2)
      checked = set()
      dic = {}

      def check(i, j):
        count = 0
        while  i < end1 and j < end2 and ((i,j) not in checked) and s1[i] == s2[j]:
          checked.add((i, j))
          i += 1
          j += 1
          count += 1
        return count

      
      for i in range(end2):
        alp = s2[i]
        if alp in dic:
          dic[alp].append(i)
        else:
          dic[alp] = [i]

      ans = 0

      for i in range(end1):
        alp = s1[i]
        if alp in dic:
          lst = dic[alp]
          for j in lst:
            if not ((i, j) in checked):
              a = check(i, j)
              if a > ans:
                ans = a

      print(ans)
    except EOFError:
      break
solve()

Submission status: Memory Limit Exceeded

Solution code:
while True:
    try:
        s = raw_input()
        t = raw_input()
    except:
        break

    ans = 0

    dp = [[0] * (len(t) + 1) for x in xrange(len(s) + 1)]

    for i in xrange(len(s)):
        for j in xrange(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            ans = max(ans, dp[i + 1][j + 1])

    print ans

Submission status: Memory Limit Exceeded

Solution code:


while True:
  try:
    a = raw_input()
    b = raw_input()
    ans = 0
    dp = [[0 for j in range(4001)] for i in range(4001)]
    for i in range(1, len(a) + 1):
      for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
          dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1, dp[i - 1][j])
          ans = max(ans, dp[i][j])
        else:
          dp[i][j] = 0
    print ans
  except EOFError:
    break

Submission status: Memory Limit Exceeded

Solution code:


dp = [[0 for j in range(4001)] for i in range(4001)]
while True:
  try:
    a = raw_input()
    b = raw_input()
    ans = 0
    for i in range(1, len(a) + 1):
      for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
          dp[i][j] = dp[i - 1][j - 1] + 1
          ans = max(ans, dp[i - 1][j - 1] + 1)
        else:
          dp[i][j] = 0
    print ans
  except EOFError:
    break

Submission status: Accepted

Solution code:
while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        if len(s1) < len(s2): s1,s2 = s2,s1
        l = sum(min(s1.count(i), s2.count(i)) for i in set(list(s1)) & set(list(s2)))
        if l == 0: print 0; continue
        ans = 0
        for i in range(len(s2)):
            if len(s2) - i <= ans: break
            for j in range(ans+1, min(l + 1,len(s2)-i+1)):
                if s2[i:i+j] in s1:
                    ans = j
                else: break
        print ans
    except:
        break

Submission status: Accepted

Solution code:
while 1:
    try:s=input()
    except:break
    t=input()
    if len(s)<len(t):s,t=t,s
    a=sum(min(s.count(i),t.count(i)) for i in set(s)&set(t))
    b=0
    for x in range(len(t)):
        if len(t)-x<=b:break
        for y in range(b+1,min(a+1,len(t)-x+1)):
            if t[x:x+y] in s:b=y
            else:break
    print(b)

Submission status: Accepted

Solution code:
def rolling_hash(S, base, MOD):
    l = len(S)
    h = [0]*(l + 1)
    for i in range(l):
        h[i+1] = (h[i] * base + ord(S[i])) % MOD
    return h


C = open(0).read().split()
MOD = 358976445361682909
base = 31
for t in range(len(C)//2):
    S = C[2*t]; T = C[2*t+1]
    rhs = rolling_hash(S, base, MOD)
    rht = rolling_hash(T, base, MOD)
    L = len(S); M = len(T)
    def solve(l):
        v = pow(base, l, MOD)
        hs = set()
        for i in range(L-l+1):
            hs.add((rhs[i+l] - rhs[i]*v) % MOD)
        for i in range(M-l+1):
            if (rht[i+l] - rht[i]*v) % MOD in hs:
                return 1
        return 0
    left = 0; right = min(L, M)+1
    while left+1 < right:
        mid = (left + right) // 2
        if solve(mid):
            left = mid
        else:
            right = mid
    print(left)

Submission status: Accepted

Solution code:
# coding:utf-8
from __future__ import division, print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass

p, q = 10 ** 9 + 7, 0xffffffff
pow_p = [1]
for i in range(4010):
    pow_p.append(pow_p[-1] * p & q)


def exists(a, b, k):
    n, m = len(a), len(b)

    s = [a[k + i] - a[i] * pow_p[k] & q for i in range(n - k)]
    t = [b[k + i] - b[i] * pow_p[k] & q for i in range(m - k)]
    return len(set(s).intersection(set(t))) > 0


def hash(s):
    t = 0
    yield t
    for c in s:
        t = t * p + ord(c) & q
        yield t
    return


def solve(s, t):
    n, m = len(s), len(t)
    a, b = list(hash(s)), list(hash(t))

    l, r = 0, min(n, m) + 1
    while l + 1 < r:
        m = (l + r) // 2
        if exists(a, b, m):
            l = m
        else:
            r = m
    return l


while True:
    try:
        s = input().strip()
        t = input().strip()
    except EOFError:
        break

    print(solve(s, t))

Submission status: Accepted

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			if len(t) - sp <= ans:
				break
			for L in range(ans,len(t)-sp+1):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		ans = 0
		for sp in range(len(t)):
			if len(t) - sp <= ans:
				break
			for L in range(ans+1,len(t)-sp+1):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		s,t = raw_input(),raw_input()
		if len(s) < len(t): s,t = t,s
		MAXL = sum(min(s.count(i),t.count(i)) for i in set(list(s))&set(list(t)))
		ans = 0
		for sp in range(len(t)):
			if len(t) - sp <= ans:
				break
			for L in range(ans+1,min(MAXL+1,len(t)-sp+1)):
				if t[sp:sp+L] in s:
					ans = L
				else:
					break
		print ans
	except:
		break

Submission status: Accepted

Solution code:
while True:
  try:
    s, t = raw_input(), raw_input()
    if len(s) < len(t): s, t = t, s
    MAXL = sum(min(s.count(i), t.count(i)) for i in set(list(s)) & set(list(t)))
    ans = 0
    for sp in range(len(t)):
      if len(t) - sp <= ans:
        break
      for l in range(ans+1, min(MAXL+1, len(t)-sp+1)):
        if t[sp:sp+l] in s:
          ans = l
        else:
          break
    print ans
  except:
    break

Submission status: Accepted

Solution code:
while True:
    try:
        s1 = input()
    except EOFError:
        break
    s2 = input()
    BASE = 27
    MOD = 1000000007


    def rolling_hash(s):
        h_lst = [0]
        for c in s:
            h_lst.append((h_lst[-1] * BASE + ord(c)) % MOD)
        return h_lst


    h_lst1 = rolling_hash(s1)
    h_lst2 = rolling_hash(s2)
    length1 = len(s1)
    length2 = len(s2)

    pow_mem = [pow(BASE, i, MOD) for i in range(min(length1, length2) + 1)]


    def check(center):
        hash_set = {(h_lst1[i + center] - h_lst1[i] * pow_mem[center]) % MOD for i in range(length1 - center + 1)}
        for i in range(length2 - center + 1):
            h2 = (h_lst2[i + center] - h_lst2[i] * pow_mem[center]) % MOD
            if h2 in hash_set:return True
        return False


    left = 0
    right = min(length1, length2)
    while right > left + 1:
        center = (left + right) // 2
        if check(center):
            left = center
        else:
            right = center
    print(right if check(right) else left)

Submission status: Runtime Error

Solution code:


while True:
  try:
    a = raw_input()
    b = raw_input()
    ans = 0
    dp = [[0 for j in range(4000)] for i in range(4000)]
    for i in range(1, len(a) + 1):
      for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
          dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1, dp[i - 1][j])
          ans = max(ans, dp[i][j])
        else:
          dp[i][j] = 0
    print ans
  except EOFError:
    break