python 3.6, 앞에서부터 문자열을 구하여 집합으로 묶고, 두집합의 교집합의 max 를 구함. 없으면 0

def set_str_array(s):
    return {s[i:j] for i in range(len(s)) for j in range(i, len(s)+1)}


in1 = input("string1: ")
in2 = input("string2: ")

result = max(set_str_array(in1) & set_str_array(in2))

print("\n%d\n'%s'" % (len(result), result))

실행결과

string1:  photography
string2:  autograph

7
'tograph'

string1:  qwer
string2:  abcd

0
''

def word_char(word):
    charlst = [ x for x in word ]
    word_list = []
    length = len(word)
    for i in range(0,length):
        a = ""
        for j in range(i,length):
            a = a + charlst[j]
            if a != "" : word_list.append(a)
    return word_list

def com_word(word1, word2):
    word1_char = word_char(word1)
    word2_char = word_char(word2)
    longest = ""
    for i in range(0,len(word1_char)):
        for j in range(0,len(word2_char)):
            if word1_char[len(word1_char)-i-1] == word2_char[len(word2_char)-j-1]:
                if len(longest) <= len(word1_char[len(word1_char)-i-1]):
                    longest = word1_char[len(word1_char)-i-1]
    print (len(longest))
    print (longest)

com_word('photography', 'autograph')

PHP로 비교회수를 줄이는데 중점을 두고 짜봤습니다.

$str1 = "photography";
$str2 = "autograph";


if(strlen($str1)>strlen($str2)) {
    $string_long = $str1;
    $string_short = $str2;
} else {
    $string_long = $str2;
    $string_short = $str1;
}
$length = strlen($string_short);

$found = FALSE;
for($i=$length; $i>=1 && !$found; $i--) {
    $idx = 0;
    while(strlen($tmp = substr($string_short,$idx, $i))==$i && !$found) {
        if(strpos($string_long, $tmp)!==FALSE) {
            echo $i."<br>".$tmp;
            $found = TRUE;
        }
        $idx++;
    }
}

Haskell로 작성하였습니다.

import Data.List

getTokens xs n = [take n (drop i xs) | i <- [0..(length xs - n)]]

findCommonString s1 s2 = if length result > 0 then head result else ""
    where
        (shortStr, longStr) = if length s1 < length s2 then (s1, s2) else (s2, s1)
        shortLength = length shortStr
        result = [token | n <- reverse [1..shortLength], token <- getTokens shortStr n, isInfixOf token longStr]

-- let's find common string.     
main = return $ findCommonString "photography" "autograph"

Ruby

1. stdin을 2회 입력받아 길이가 작은 문자열을 a, 긴 문자열을 b로 합니다.
2. cmn - 문자열 a의 s란 인덱스에서 시작해서 만들어지는 부분 문자열중 b에 속하는 가장 긴 문자열을 돌려주는 함수입니다. 입력 s, 출력 s로 시작하는 가장 긴 공통문자열(b에 속하지 않는 문자열이 발견되는 경우 break로 중단한 뒤 직전의 공통 문자열 리턴)
3. lcs - cmn[시작인덱스]를 호출, cmn으로 획득한 문자열과 임시변수 gcs(최장공통부분문자열)중 긴 문자열을 gcs에 저장합니다. a문자열 길이만큼 반복하면 lcs에 최장공통부분문자열이 남습니다.
4. lcs의 길이와 문자열을 한줄씩 번갈아가며 출력합니다.

def longest_common_str
  a,b = (1..2).map {gets.chop}.sort_by(&:size)
  cmn = ->s { (s...a.size).reduce("") {|_,e| b.include?(a[s..e])? a[s..e] : break } }
  lcs = (0...a.size).reduce("") {|gcs,s| [gcs, cmn[s]||""].max_by(&:size) }
  puts lcs.size, lcs
end

Test

$stdin = StringIO.new("photography\nautograph\n") # for stdin
expect{ longest_common_str }.to output("7\ntograph\n").to_stdout

Output

longest_common_str
photography
autograph

7
tograph

C언어로 작성, 맞을지 모르겠네요...틀린부분 댓글 플리즈 모든 경우의 수를 다 구해서 비교하기 보다는 최대한 조금이라도 시간복잡도를 줄여보고자 했어요, O(n)에는 못하겠네요... 누가 찾아 주세요.

#include <stdio.h>
int main(){
    char* a = "photography";
    char* b = "autograph";
    char ms[4000] = "";

    char* pa = a;
    char* pb = b;
    char* bm = pa;

    int s = 0;
    int m = 0;

    while(*pa != '\0') {
        if(*pa == *pb){
            pa++; pb++; s++;
            if(s > m){
                m = s;
                for(int i=0;i<s;i++){
                    ms[i] = *(bm + i);
                }
                ms[s] = '\0';
            }
        }else{
            pa = bm;
            if(s == 0){
                pb++;
            }
            s = 0;
        }       
        if(*pb == '\0'){
            pb = b;
            pa = ++bm;
        }
    }
    printf("%d\n%s", m, ms);
}

ruby 풀이를 보고 c# lamda로 구현해봄. 중간에 파이프라인이 끊어짐... 붙일수가 없음.. ㅠㅠ

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = "autograph";
            string b = "photography";
            Func<int, List<string>> cmn = (s) => {
                return Enumerable.Range(s, a.Length - s).Select(
                    e => b.Contains(a.Substring(s, e - s + 1)) ? a.Substring(s, e - s + 1) : ""
                ).ToList<string>();
            };
            List<string> cs_lst = new List<string>();
            for (int i = 0; i < a.Length; i++)
            {
                cs_lst.AddRange(cmn(i).ToArray());
            }
            string lcs = cs_lst.OrderByDescending(x => x.Length).First();
            Console.WriteLine(lcs.Length);
            Console.WriteLine(lcs);
            Console.ReadKey();
        }
    }
}

Java 풀이입니다

public static void main(String[] args) { // TODO Auto-generated method stub /* * photography * autograph /

    String first = "photography";
    String second = "autography";

    int longestCommon = 0;
    int compareValue = 0;
    String commonstring = null;

    for(int i = 0 ; i < first.length() ; i++){

        for(int j = 0 ; j < second.length() ; j++){

            if(first.charAt(i) == second.charAt(j)){

                int minoftwo = Math.min(first.length(), second.length());
                String common = "";

                for(int k = 0 ; k < minoftwo  ; k++){

                    try{
                        if(first.charAt(i+k)==second.charAt(j+k)){
                            common=common.concat(String.valueOf(first.charAt(i+k)));
                            longestCommon++;
                        }
                    }catch(StringIndexOutOfBoundsException e){

                    }


                }
                if(longestCommon > compareValue){
                    compareValue = longestCommon;
                    commonstring = common;
                }
                longestCommon=0;
            }

        }

    }
    System.out.println(commonstring+" 공통 문자열");
    System.out.println(compareValue+" 공통 문자열 길이");
}

재밌어보여서 저도 한번 ㅎㅎ

std::string codeingdojang(std::string w1, std::string w2, int *length)
{
    int longest_len = 0;
    std::string result;

    for (size_t n = 0; n < w1.length(); n++)
    {
        int search_len = 0;
        std::string search_word;

        for (char c2 : w2)
        {
            char c1 = '\0';
            if (n + search_len < w1.length())
                c1 = w1.at(n + search_len);

            if (c1 == c2)
            {
                search_len++;
                search_word.push_back(c1);
            }
            else
            {
                if (search_len > longest_len)
                {
                    longest_len = search_len;
                    result = search_word;
                }
                search_len = 0;
                search_word.clear();
            }
        }

        if (search_len > longest_len)
        {
            longest_len = search_len;
            result = search_word;
        }
    }

    if (length != nullptr)
        *length = longest_len;
    return result;
}

Python 3

def findCommonString(s, lowerLengthString):
    if len(lowerLengthString) > len(s):
        s, lowerLengthString = lowerLengthString, s

    n = len(lowerLengthString)
    for i in range(n):
        for j in range(i+1):
            token = lowerLengthString[j:n-i+j]
            if token in s:
                print(len(token))
                print(token)
                return
    else:
        print("Not found.")

# let's find common string.
findCommonString("photography", "autograph")

Result

7
tograph

전 부분집합으로 저장해서 찾아봤어요.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Subset {


    static Set textSet1 = new HashSet<>();
    static Set textSet2 = new HashSet<>();
    static Set sameSet = new HashSet<>();

    public Set findSameSet(Set set1, Set set2){  // 똑같은 부분을 찾고 그중 긴 걸 찾는다.
        Set result = new HashSet<>(); 

        for(Object str : set1){
            if(set2.contains((String)str)){    
                result.add(str); 
            }
        }         
        return result;
    }

    public String findMaxSameSet(Set gemeinsamSet){ // 가장 긴 원소찾기

        Iterator it = gemeinsamSet.iterator();
        String el = "";

        while(it.hasNext()){
            el = (String) it.next(); 
            if(el.length()==findMaxIndexOfSet(gemeinsamSet)){
                return el;
            }
        }

        return "Not found.";
    }

    public int findMaxIndexOfSet(Set gemeinsamSet){
        Iterator it = gemeinsamSet.iterator();
        String el = "";
        int max = 0;
        while(it.hasNext()){
            el = (String) it.next(); 
            if(el.length()>max)
                max = el.length();
        }
        return max;
    }

    public Set doSubset(String text){
        Set stringSet = new HashSet<>();
        int count = 0;
        while(count<text.length()){

            for (int i = 0; i < text.length(); i++) {
                split(count, text, i, stringSet); 
            }
            count++;
        }
        return stringSet;
    }

    public void split(int count, String text, int index, Set stringSet){
        String temp = "";
        for (int i = index; i <= count; i++) {
            temp+=text.charAt(i);
        }
        stringSet.add(temp);
    }

    public static void main(String[] args) {
        Subset ss = new Subset();
        String text1 = "photograph";
        String text2 = "autograph";
        textSet1 = ss.doSubset(text1);
        textSet2 = ss.doSubset(text2);
        sameSet =ss.findSameSet(textSet1, textSet2);
        System.out.println("동일한 부분: " + sameSet);
        String result = ss.findMaxSameSet(sameSet);
        System.out.println("동일하면서 가장 긴 부분: " + result);
    }
}

C++ Code

다이나믹 프로그래밍을 이용해서 최장공통부분열의 길이를 찾고 문자열을 dp테이블을 이용해서 reconstruct 하는 방법으로 코딩해봤습니다. 시간복잡도는 첫번째 문자열의 길이 n, 두번째 문자열의 길이 m이라고 가정했을때 O(mn) 입니다.

#include <iostream> 
#include <string> 
#include <algorithm> 
using namespace std; 

int m,n;  
int lcs[1001][1001];  

int Len(string s1,string s2){
    for (int i = m; i >= 0; i--){
        for (int j = n; j >= 0; j--){
            if (i == m || j == n){
                lcs[i][j] = 0; 
            }else if (s1[i] == s2[j]){
                lcs[i][j] = 1+lcs[i+1][j+1];  
            }else{
                lcs[i][j] = max(lcs[i+1][j],lcs[i][j+1]);  
            }
        }
    }
    return lcs[0][0];  
}

string actual(string s1, string s2){
    string t = "";  
    int i = 0, j = 0;  
    while (i < m && j < n){
        if (s1[i] == s2[j]){
            t += s1[i]; 
            i++, j++;  
        }else if (lcs[i+1][j] >= lcs[i][j+1]){
            i++; 
        }else{
            j++; 
        }
    }
    return t; 
}

int main(){
    string s1,s2; 
    cin >> s1 >> s2; 
    m = (int)s1.size();  
    n = (int)s2.size();  
    int ans = Len(s1,s2); 
    string actualLCS = actual(s1,s2); 
    cout << ans << endl; 
    cout << actualLCS << endl; 
    return 0; 
}    

def d(s):
    res = set('')
    for i in range(len(s)):
        for j in range(len(s)-i):
            res.add(s[j:j+i+1])
    return res

def c(a, b):
    M = 0; s = ''
    for i in d(a)&d(b):
        if M < len(i):
            M = len(i)
            s = i
    return '%d\n%s'%(M, s)

while __name__ == '__main__':
    print(c(input(), input()))

루프문은 각 나누기마다 n(n+1)/2번으로 시간복잡도는 크긴 합니다만, 사전에서 가장 긴 영단어가 45자이고, 122자리로 테스트해봐도 답이 즉시 나와서 최적화할 필요는 없는 것 같습니다.

파이썬 3.5.2 64

Javascript

Function

function getLongerCommonStr(input1, input2){
  var shorter = (input1.length <= input2.length)? input1 : input2;
  var longer = (input1.length > input2.length)? input1 : input2;
  var diff = longer.length - shorter.length + 1;

  for(var i = 0; i < shorter.length; i++){
    for(var j = 0; j < i + diff; j++){
      var part = longer.substr(j, shorter.length - i);
      if(shorter.indexOf(part) != -1){
        return part;
      }
    }

  }
  return undefined;
}

Test

var str1 = "photography";
var str2 = "autograph";

var result = getLongerCommonStr(str1, str2);

console.log(result.length);
console.log(result);

JAVA

두 문자열에서 짧은 쪽의 길이를 저장합니다. 이 길이로 각 문자열을 잘라서 Set에 넣습니다. Set에 넣을 때 충돌되면 공통 문자열이라 볼 수 있죠. DFS로 찾게 됩니다.

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class LongestCommonString {

    static Set<String> stringParts = new HashSet<>();
    static String LCS = "";

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String input1 = args[0];
        String input2 = args[1];
        int length = (args[0].length() < args[1].length())?
                args[0].length(): args[1].length();
        while(length > 0) {
            if (!addSet(input1, length) || !addSet(input2, length)) {
                break;
            }
            length--;
        }
        System.out.println(length);
        System.out.println(LCS);
    }


    private static boolean addSet(String str, int size) {
        Queue<Vector<Integer>> q = new LinkedBlockingQueue<>();
        String cap;
        int idx = 0;


        while(idx + size <= str.length()) {
            cap = str.substring(idx, idx+size);
            if (stringParts.contains(cap))  {
                LCS = cap;
                return false;
            } else  {
                stringParts.add(cap);
            }
            idx++;
        }
        return true;
    }

}


//private static void printSet() {
//  Iterator iterator = stringParts.iterator();
//  while(iterator.hasNext()) {
//      System.out.println("" + iterator.next());
//  }
//  System.out.println();
//}

파이썬입니다. 짧은 문자열의 부분문자열을 긴 것부터 생성하는 제너레이터를 이용해서 찾도록했습니다.

def g(s):
    l = len(s)
    i, m = 0, l
    while m > 0:
        yield s[i:m+i]
        i += 1
        if m + i - 1 > l:
            i, m = 0, m -1


def do(a, b):
    a, b = (a, b) if len(a) > len(b) else (b, a)
    for m in g(b):
        if m in a:
            print(len(m))
            print(m)
            break

a, b = input(), input()
do(a, b)

4000자 짜리 랜덤 스트링을 두개 만들어서 해보니 1분 나오네요 ㅠㅠㅠㅠ

#파이썬 3.5.2
#각 문자열의 부분문자열을 찾은 뒤 공통된 것중 긴것을 출력. 공통된 것을 찾는 것은 집합 형태를 이용했다.
def part(s):
    re = []
    for i in range(1,len(s)+1):
        for j in range(i):
            re.append(s[j:j+len(s)-i+1])
    return re

a = input()
b = input()
alist = set(part(a))
blist = set(part(b))
answers = alist.intersection(blist)
answer = max(answers,key=len)
print(len(answer))
print(answer)

이중/삼중 루프를 피하는 방법은 잘 모르겠고..

int main(int argc, const char * argv[]) {
    lcs("photography", "autograph");
    return 0;
}

우선 가장 쉬운 방법으로 풀어보자. 두 문자열의 시작점을 하나씩 옮겨가면서 비교하여 가장 긴 공통문자열을 찾으면 된다.

void lcs(const char* s1, const char* s2) {
    size_t len = strlen(s1);
    size_t maxIndex = 0;
    size_t max = 0;

    for (size_t i=0; i<len;) {
        size_t len2 = lcs1(s1 + i, s2); // s1에 대해 하나씩 검사
        if (len2 > max) {
            maxIndex = i;
            max = len2;
        }
        i += len2 ? len2 : 1; // 공통문자열만큼 건너뛴다.
    }

    printf("%.*s\n", (int)max, s1 + maxIndex);
}

lcs1은 두번째 인자에 대해 하나씩 검사한다.

size_t lcs1(const char* s1, const char* s2) {
    // s1을 s2에서 찾자
    size_t len = strlen(s2);
    size_t max = 0;
    for (size_t i=0; i<len; ) {
        size_t len2 = lcs2(s1, s2 + i); // s2에 대해 하나씩 검사
        if (len2 > max) {
            max = len2;
        }
        i += len2 ? len2 : 1; // 마찬가지로 찾은 길이만큼 건너뛴다.
    }
    return max;
}

마지막으로 lcs2는 시작점을 기준으로 공통문자열의 길이만 찾으면 된다.

size_t lcs2(const char* s1, const char* s2) {
    size_t len = 0;
    while (*s1 && *s2 && *s1 == *s2) {
        len++;
        s1++;
        s2++;
    }
    return len;
}

이상의 코드에서 lcs2의 호출을 살펴보면.. 아래와 같은 식으로 검사한다.

photography autograph -> 0
photography utograph -> 0
photography tograph -> 0
photography ograph -> 0
photography graph -> 0
photography raph -> 0
photography aph -> 0
photography ph -> 2
otography autograph -> 0
otography utograph -> 0
otography tograph -> 0
otography ograph -> 1
otography graph -> 0
otography raph -> 0
otography aph -> 0
otography ph -> 0
otography h -> 0             <- 벌써 2라는 최대값을 알기 때문에 검사할 필요 없다!
tography autograph -> 0
tography utograph -> 0
tography tograph -> 7
y autograph -> 0             <- 벌써 7이라는 최대값을 알기 때문에 더이상 검사할 필요 없다!
y utograph -> 0
y tograph -> 0
y ograph -> 0
y graph -> 0
y raph -> 0
y aph -> 0
y ph -> 0
y h -> 0

이미 확인된 최대값을 알면 가지치기를 조금 더 할 수 있다.

void lcs(const char* s1, const char* s2) {
    size_t len = strlen(s1);
    size_t maxIndex = 0;
    size_t max = 0;

    for (size_t i=0; i<len - max;) {      // s1이 max보다 짧아지면 더 검사할 필요없다.
        size_t len2 = lcs1(s1 + i, s2, max);
        if (len2 > max) {
            maxIndex = i;
            max = len2;
        }
        i += len2 ? len2 : 1;
    }

    printf("%.*s\n", (int)max, s1 + maxIndex);
}

lcs1에 대해서도..

size_t lcs1(const char* s1, const char* s2, size_t knownMax) {
    // s1을 s2에서 찾자
    size_t len = strlen(s2);
    size_t max = 0;
    for (size_t i=0; i<len - knownMax; ) { // 이미 알고 있는 max만큼이 될 여지 가 없으면 중단한다.
        size_t len2 = lcs2(s1, s2 + i);
        if (len2 > max) {
            max = len2;
            if (max > knownMax) {
                knownMax = max;
            }
        }
        i += len2 ? len2 : 1;
    }
    return max;
}

그러면 lcs2가 호출되는 횟수를 줄일 수 있다.

photography autograph -> 0
photography utograph -> 0
photography tograph -> 0
photography ograph -> 0
photography graph -> 0
photography raph -> 0
photography aph -> 0
photography ph -> 2
otography autograph -> 0
otography utograph -> 0
otography tograph -> 0
otography ograph -> 1
otography graph -> 0
otography raph -> 0
otography aph -> 0
tography autograph -> 0
tography utograph -> 0
tography tograph -> 7

def do(a, b):
    if a == '' or b == '':
        return
    def _subset(s):
        return set([s[x:y] for x in range(len(s))
                                    for y in range(x, len(s) + 1)])
    r = list(_subset(a) & _subset(b))
    r.sort(key=lambda x:len(x), reverse=True)
    print('{}\n{}'.format(len(r[0]), r[0]))         

do('photography', 'autograph')

또는

def subset(str_):
    len_ = len(str_)
    l = len_
    while l > 0:
        for x in range(0, (len_ - l) + 1):
            yield str_[0 + x:l + x]
        l-=1

def do(a, b):
    src = a
    cmp = b
    if len(cmp) > len(src):
        src, cmp = cmp, src
    for x in subset(cmp):
        if src.find(x) != -1:
            print('{}\n{}'.format(len(x), x))
            break

do('photography', 'autograph')

Python 3.5.2에서 작성하였습니다.

include

include

int main() { char str1[4001], str2[4001]; fgets(str1, sizeof(str1), stdin); fgets(str2, sizeof(str2), stdin); str1[strlen(str1)-1] = '\0'; str2[strlen(str2)-1] = '\0'; if (strlen(str1) < strlen(str2)) { char tmp[4001]; strcpy(tmp, str1); strcpy(str1, str2); strcpy(str2, tmp); }

int i, j, n = strlen(str2);
while(n > 0) {
    for (i = 0; i <= strlen(str2)-n; i++) {
        for (j = 0; j <= strlen(str1)-n; j++) {
            if (strncmp(str1+j, str2+i, n) == 0) {
                char tmp[4001];
                strncpy(tmp, str1+j, n);
                tmp[n] = '\0';
                printf("%d\n", n);
                printf("%s\n", tmp);
                return 0;
            }
        }
    }
    n--;
}
printf("%d\n", 0);
return 0;

}

str1 = 'photography'
str2 = 'autograph'
step, length, string = 0, list(), list()
for x in range(len(str1)):
    if step <= x:
        for y in range(len(str2)):
            if str1[x] == str2[y]:
                for a in range(1, len(str1[x:])+1):
                    if str1[x:x+a] != str2[y:y+a]:
                        length.append(len(str1[x:x+a-1]))
                        string.append(str1[x:x+a-1])
                        step = x+a
                        break
print(max(length))
print(string[length.index(max(length))])

#### 2017.01.25 D-393 ####

def LCW_solver(s1, s2, s=""):
    def LCW(s1, s2):
        if len(s1)*len(s2)==0 or s1[0]!=s2[0]: return ""
        else: return s1[0] + LCW(s1[1:],s2[1:]) 
    for i1 in range(len(s1)):
        for i2 in range(len(s2)):
            ns=LCW(s1[i1:],s2[i2:])
            if len(s)<len(ns): s=ns
    return s

print(LCW_solver("photography", "autograph"))

def subset_string(data):
    result=[]
    for i in range(len(data)-1):
        for j in range(i,len(data)+1):
            result+=[data[i:j]]
    return set(result)

def strings(data):
    inter_set=subset_string(data[0]).intersection(subset_string(data[1]))
    leng1=['',0]
    for i in inter_set:
        if leng1[1]<len(i):
            leng1=[i,len(i)]
    print("%d\n%s"%(leng1[1],leng1[0]))

strings(["photography","autograph"])

import java.util.Scanner;

import static java.lang.System.in;

public class PartialTextSearch {

    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String text = sc.next();
        String pattern = sc.next();
        int p = pattern.length();
        int max = 0;
        String result = "";
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < p; j++) {
                if (i < j) {
                    String pp = pattern.substring(i, j + 1);
                    if (text.indexOf(pp) != -1 && max < pp.length()) {
                        max = pp.length();
                        result = pp;
                    }
                }
            }
        }
        System.out.println(max);
        System.out.println(result);
    }
}

def longest_mached_chars(words):
    # 단어의 부분을 취할때 적게 루프를 돌기 위해 짧은 단어기준으로 돌도록
    short_word = words[1] if len(words[0]) > len(words[1]) else words[0]
    long_word = words[0] if short_word == words[1] else words[1]
    longest_match = ''
    for idx in range(0, len(short_word)):
        for l in range(1, len(short_word) - idx + 1):
            chars = short_word[idx:idx+l]
            if chars in long_word:
                if len(longest_match) < len(chars):
                    longest_match = chars
    print(len(longest_match))
    print(longest_match)

longest_mached_chars(['photography', 'autograph'])

package hellojava;

import java.util.ArrayList;

public class practice {
    static ArrayList vocSplit(String str) {
        ArrayList<String> listStr = new ArrayList<String>();
        for (int i = 0; i < str.length(); i++) {
            for (int k = 0; k < str.length() - i; k++) {
                listStr.add(str.substring(k, k + i + 1));
            }
        }
        return listStr;
    }

    public static void main(String[] args) {
        ArrayList<String> voc1 = new ArrayList<String>();
        ArrayList<String> voc2 = new ArrayList<String>();
        ArrayList<String> collectedVoc = new ArrayList<String>();

        try {
            voc1 = practice.vocSplit("photography");
            voc2 = practice.vocSplit("autograph");

            for (int i = 0; i < voc1.size(); i++) {
                if (voc2.contains(voc1.get(i)) == true) {
                    collectedVoc.add(voc1.get(i));
                }
            }
            System.out.println(collectedVoc.get(collectedVoc.size() - 1));

        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("no common subset");
        }
    }
}

코딩이 지저분하네요

a="photography"
b="autograph"
a_list=[] # a 문자열 집합용
b_list=[] # b 문자열 집합용
c_list=[] # a,b 문자열 비교하여 같은거 집합용
d_list=[] # 가장 큰 문자 갯수용
temp_list=[]
for i in range (0, len(a)):
    for k in range (1,len(a)):
        a_list.append(a[i:k])

for i in range (0, len(a)):
    for k in range (1,len(a)):
        b_list.append(b[i:k])

for i in range (0, len(a_list)):
    for k in range (1,len(b_list)):
        if(a_list[i]==b_list[k] and b_list[k]!=""):
            c_list.append(b_list[k])

for i in range (0, len(c_list)):
    d_list.append(int(len(c_list[i]))) #문자열 크기 구하기
    temp_list.append(int(len(c_list[i]))) #소팅하기전 문자 구하기


d_list.sort() #문자열크기  소팅

print(d_list[-1]) # 가장큰 문자의 갯수 출력
c_index=temp_list.index(d_list[-1]) #가장큰 문자의 index 확인
print(c_list[c_index]) # 가장큰 문자 출력

7
tograph

Python 3으로 풀었습니다.

def longest_common_substring(s1, s2):
    if len(s1) < len(s2):
        tmp = s1
        s1 = s2
        s2 = tmp

    for size in range(len(s2), 0, -1):
        for s in range(len(s2) - size + 1):
            if s2[s:s+size] in s1:
                return s2[s:s+size]

s1, s2 = 'photography'+'!', 'autograph'+'@'
l1, l2 = len(s1), len(s2)
lcs = ''
for i in range(l1):
    for j in range(l2):
        for k in range(min(l1-i, l2-i)+1):
            if s1[i+k] != s2[j+k]:
                if k > len(lcs):
                    lcs = s1[i:i+k]
                break

print(lcs, len(lcs)) # tograph 7

# python 3.6
import itertools as it


def subsets(inp):
    """return the list of inp subsets for a given inp"""
    # 입력 문자열에 대해 길이 별 부분집합 문자(열) 생성(문자열 내 순서대로 포함 조건)
    return ["".join(tp) for i in range(len(inp) + 1)
            for tp in list(it.combinations(inp, i)) if "".join(tp) in inp]


st1 = input("string 1: ")
st2 = input("string 2: ")
# 부분 문자열으 교집합 중 최대 길이
cmn = max(set(subsets(st1)) & set(subsets(st2)))
print("%d\n%s" % (len(cmn), cmn))

inp = 'photography\nautograph'
(str1, str2) = inp.split()
if len(str2) > len(str1):
    str1, str2 = str2, str1

maxl = 0
maxsc = ''
for l in range(1, len(str2)+1):
    for i in range(len(str2)):
        sc = str2[i:i+l]
        if str1.count(sc) and len(sc) > maxl:
            maxl = len(sc)
            maxsc = sc

print(maxl, maxsc)

파이썬 3.6

def part(string):
    part,n = [],2
    for i in string:
        part.append(i)
    while n <= len(string)-1:
        for h in range(len(string)-n):
            part.append(string[h:h+n+1])
        n += 1
    return part

def overlappart(data):
    overlapset = set(part(data[0])) & set(part(data[1]))
    partlist.extend(list(overlapset))
    for sub_part in partlist:
        length.append(len(sub_part))

if __name__ == "__main__":
    data = ['photography','autograph']
    partlist,overlap,length = [],[],[]
    overlappart(data)
    print(max(length))
    print(partlist[length.index(max(length))])

*결과값

7
tograph

in 을 써버리니까 너무 간단해지네요.

긴 것 부터 찾으면 단어 갯수도 마지막 한번만 세면 됩니다.

# 파이썬

def common_string(long, short):
    if len(long) < len(short):
        return common_string(short, long)

    short_length = len(short)
    for m in range(short_length, 0, -1):
        for n in range(short_length - m): 
            short_part = short[n:n+m]
            if short_part in long: 
                return short_part, len(short_part)


print(common_string("photography", "autography"))

def substring(a):
    l = list()
    for i in range(1,len(a)+1):
        for j in range(len(a)+1-i):
            l.append(a[j:j+i])
    return l
def common(a, b):
    c = max(set(substring(a)) & set(substring(b)))
    return len(c), c

print(common('photography', 'autograph'))

def samepiece(a, b):
    apieces = []
    for anum in range(len(a)):
        args = [a[x:x+anum+1] for x in range(len(a)-anum)]
        apieces.extend(args)
    bpieces = []
    for bnum in range(len(b)):
        brgs = [b[x:x+bnum+1] for x in range(len(b)-bnum)]
        bpieces.extend(brgs)
    result = sorted(list(set(apieces) & set(bpieces)), key=len, reverse=True)[0]
    return str(len(result)) + '\n' + result
print(samepiece('photography', 'autography'))

Python 3 apieces, bpieces가 a, b의 부분문자열들이고 set로 변환하여 교집합을 구한 뒤 다시 리스트로 전환, 길이를 기준으로 리버스정렬

def partition(string,string2):

    start = 0
    finish = 1
    lst = []

    while True:
        cnt = string[start:finish+1]
        if cnt in string2:
            lst.append(cnt)
        finish += 1

        if finish == len(string):
            start += 1
            finish = start + 1

        if start == len(string) - 2:
            break

    res = sorted(lst,key = lambda x: len(x))

    print(len(res[-1]))
    return res[-1]




i1 = input()
i2 = input()

print(partition(i1,i2))

public class Pratice {
    public static void main(String[] args) {
        String[] str = { "photography", "autograph", "" };
        for (int i = 0; i < str[0].length(); i++) {
            for (int j = i; j < str[0].length(); j++) {
                if (str[1].contains(str[0].substring(i, j)) && str[2].length() < str[0].substring(i, j).length())
                    str[2] = str[0].substring(i, j);
            }
        }
        System.out.println(str[2].length() + "\n" + str[2]);
    }
}

#include <stdio.h>

int main() {
    char str1[] = "photography", str2[] = "autograph";
    char tempString[2][4000] = { 0, };
    int length[2] = { 0, 0};
    int l1 = sizeof(str1) * sizeof(char), l2 = sizeof(str2) * sizeof(char), index = 0, k = -1;
    for (int i = 0; i < l1; i++) {
        while (str1[i] != str2[++k]) {}
        length[index = length[0] <= length[1] ? 0 : 1] = 0;
        for (int j = k; j < l2; j++)
            str1[i - k + j] == str2[j] ? tempString[index][length[index]++] = str1[i - k + j] : NULL;
        k = -1;
        tempString[index = length[0] <= length[1] ? 1 : 0][length[index]] = '\0';
    }
    printf("%d\n%s\n", length[index], tempString[index]);
}

Swift입니다.

주어진 두 문장에서 짧은 문장에서 부분 문자열을 추출해서 긴 문자열에 포함되어 있는지를 반복합니다. 부분 문자열은 긴것부터 짧은 것으로 찾아나갑니다.

import Foundation

var a = "photography"
var b = "autograph"

func findSamePattern(_ a: String, _ b: String) -> String {
    let longer = a.count > b.count ? a : b
    let shorter = a.count <= b.count ? a: b
    let shorterCount = shorter.count 

    for length in stride(from:shorterCount, to: 0, by: -1) {
        var startIndex = 0
        while length + startIndex < shorterCount {
            let start = shorter.index(shorter.startIndex, offsetBy: startIndex)
            let end = shorter.index(start, offsetBy: length)
            let patternFromShorter = shorter[start...end] // Partial pattern

            let patternString = String(patternFromShorter)
            if longer.range(of: patternString) != nil {
                return patternString
            }
            startIndex += 1
        }
    }
    return "" // No common pattern found
}

let foundPattern = findSamePattern(a, b)
print("\(foundPattern.count) \(foundPattern)")

결과는...

7 tograph

Python

s = ["photography", "autograph"]
ans = [set() for i in range(len(s))]
for s_i, a in enumerate(s):
    for i in range(len(a)):
        for j in range(i, len(a)):
            ans[s_i].add(a[i:j+1])
same_str = ans[0]
for a in ans:
    same_str.intersection_update(a)
max_l = 0
ans = ""
for i in same_str:
    if len(i) > max_l:
        max_l = len(i)
        ans = i
print(max_l, ans, sep="\n")

파이썬 입니다.

def substring(s1,s2):
    sub1=[]
    sub2=[]
    for n in range(len(s1),-1,-1):
        for m in range(len(s1)-n+1):
            sub1.append(s1[m:n+m])
    for n in range(len(s2),-1,-1):
        for m in range(len(s2)-n+1):
            sub2.append(s2[m:n+m])
    for sub in sub1:
        for su in sub2:
            if sub==su:
                print(len(sub),sub)
                return
substring('photography','autograph')

a = 'photography'
b = 'autograph'

def func(a,b):
    if len(a) > len(b): a,b = b,a

    for i in range(len(a)):
        l = len(a)-i
        for j in range(i+1):
            if a[j:j+l] in b: return a[j:j+l]
    return ''

r = func(a,b)
print(len(r))
print(r)

def func(a):
    return [a[j:i] for i in range(len(a)+1) for j in range(len(a))]    

a='photography'
b='autograph'
result=sorted(list((set(func(a))&set(func(b)))),key=len)[-1]
print(len(result),result,sep='\n')

python3.6

def n_string(s):

return {s[x:y]for x in range(len(s))for y in range(len(s)+1)}

a='aphotograp'

b='bphotogdf'

result=list(set(n_string(a)&n_string(b)))

result.sort(key=lambda x:len(x),reverse=True)

print('{} {}'.format(len(result[0]),result[0]))

예강효빠님에게서 아이디어를 얻었습니다.

def part(st):
    lis = []
    for i1 in range(1,len(st)+1):
        for i2 in range(len(st)):
            lis.append(st[i2:(i1+i2,i2)[i1+i2 > len(st)]])
    return [''] + list(x for x in lis if x != '')

def comps(s1,s2):
    l,s2 = [],part(s2)
    for s in part(s1):
        if s in s2:
            l.append(s)
    return list(sorted(l))[-1],len(list(sorted(l))[-1])

s1, s2 = input().split()

def string_part(s):
    return {s[i:j] for i in range(0, len(s)) for j in range(i, len(s) + 1)}

answer = max(string_part(s1) & string_part(s2))

print(len(answer))
print(answer)

def two_strings(string1, string2):
  list_string1 = {string1[i:j] for j in range(len(string1)) for i in range(j)}
  list_string2 = {string2[i:j] for j in range(len(string2)) for i in range(j)}


  same_word = ""
  max_len = 0
  for word1 in list_string1:
    for word2 in list_string2:
      if word1 == word2:
        if len(word1) > max_len:
          max_len = len(word1)
          same_word = word1

  return same_word, max_len

two_strings('photography', 'autography')
('tograph', 7)

while True:
    user1=input("Input string(1): ")
    user2=input("Input string(2): ")
    length=min(len(user1),len(user2))
    common=[]
    while True:
        test=0
        for i in range(len(user1)-length+1):
            if user1[i:i+length] in user2:
                common.append(user1[i:i+length])
                test=1
        if test:
            print(length)
            for term in common:
                print("'{}'".format(term))
            break
        length-=1
        if length==0:
            break

def SF(S,SET):
    for i in range(len(S)):
        for j in range(len(S)):
            SET.add(S[i:j])
    return SET

s1=input();s2=input()
set1=SF(s1,set());set2=SF(s2,set());set3=set1&set2

print(len(max(set3)),'\n',max(set3))

완전탐색법으로 하여보았는데요. 입력의 상한을 넘어가는 문자열을 입력하여 보니, 계산시간이 그렇게 길지는 않더군요. 그래서 그냥 이대로 제출하기로 하였읍니다.^^

def max_com(s1, s2):
    s = ''
    m = 0

    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                t = 1
                while i+t < len(s1) and j+t < len(s2):
                    if s1[i+t] == s2[j+t]: t += 1
                    else: break
                if t > m:
                    s = s1[i:i+t]
                    m = t
    print(m, s)

max_com('photography', 'autograph')

복잡한 것은 못해서.. 단순히 더 짧은 문자열의 부분집합을 모두 구한뒤에 긴 문자열에 해당 부분집합이 있는지 찾았습니다.

public class SubStr {

public void UnionStr(String str1,String str2) {
    ArrayList<String> subList;

    if( str1.length()>str2.length() )
        subList=getSubStrs(str2);
    else
        subList=getSubStrs(str1);

    String strTemp="";

    for(String subStr:subList) {
        if(str1.contains(subStr)) {
            if(strTemp.length()<subStr.length())
                strTemp=subStr;
        }
    }

    System.out.println(strTemp.length());
    System.out.println(strTemp);
}

private ArrayList<String> getSubStrs(String str){

    ArrayList<String> list=new ArrayList<>();

    for(int i=0;i<str.length()-1;i++) {
        for(int j=i+1;j<str.length();j++) {
            list.add(str.substring(i, j+1));
        }
    }
    return list;
}

}

public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String a = scan.nextLine();
        String b = scan.nextLine();

        StringBuffer bf = new StringBuffer();
        ArrayList<String> list = new ArrayList<String>();

        for(int i=0; i<a.length(); i++) {    //똑같은 부분들을 다 찾고 list에 넣습니다.
            for(int j=i; j<a.length(); j++) {
                bf.append(a.charAt(j));
                if(!b.contains(bf)) {
                    bf.delete(j-i, j-i+1);
                    break;
                }
            }
            list.add(bf.toString());
            bf.delete(0, a.length());
        }

        int count = 0;
        for(int i=0; i<list.size(); i++) {   //list에 담겨져있는 값들을 비교하고 가장 큰 길이 값을 count로 설정합니다.
            if(list.get(i).length()>=count) {
                count=list.get(i).length();
            }
        }
        System.out.println(count);       // count랑 같은 길이를 가진 값을 출력합니다.
        for(int i=0; i<list.size(); i++) {
            if(list.get(i).length()==count) {
                System.out.println(list.get(i));
            }
        }
    }
}

data1_list = []
data2_list = []
temp_list =['a']
lenth = 2
for i in range(len(data1)):
    for j in range(i+2,len(data1)+1):
        data1_list.append(data1[i:j])

for i in range(len(data2)):
    for j in range(i+2,len(data2)+1):
        data2_list.append(data2[i:j])

for i in data1_list:
    for j in data2_list:
        if i == j :
            if lenth < len(i) :
                lenth = len(i)                
                temp_list.pop()
                temp_list.append(i)
a= (",".join(temp_list))                
print(len(a))                
print(a)

string1="photography"
string2="autograph"

def MaxPartial(string): #부분문자열을 구하는 함수
    n=2
    lst=list(map(str,string))
    while n<=len(lst):
        for i in range(len(lst)): #여기서 len(lst)로 쓰면 부분문자열 리스트 요소에 ""(공백)이 하나 추가로 들어감.
            ns=string[i:i+n]
            if ns not in lst:
                lst.append(ns)
        n+=1
    return lst

elst=[]
for string in MaxPartial(string1):
    if string in MaxPartial(string2):
        elst.append(string)
print(len(elst[-1]),elst[-1]) #위의 함수에 range()를 len(lst)로 잡았기 때문에 공통된 부분이 없을 경우(실제로는 ""(공백)이라는 공통된 요소가 있음), elst=[]이 아니라 elst=[""]임. 그래서 elst[-1]을 쓸 수가 있음. 공통된 부분이 없을 경우 따라서 0을 출력함. (len(string)으로 했을 경우 ""(공백)없이 부분 문자열로만 리스트가 이루어지기 때문에 공통된 부분이 없으면 elst=[]이기 때문에 elst[-1]을 하면 오류 발생)

def comm_str():
    INP1 = input("INPUT1 : ")
    INP2 = input("INPUT2 : ")
    res = ''
    for pos in range(0, len(INP1)) :
        if INP1[pos] in INP2 : # 첫 번째 입력의 각 문자를 돌아가며, '그 문자로 시작하는 부분 문자열'이 두 번째 입력에 존재하는지 확인
            for unt in range(len(res), len(INP1)-pos) :  # 현재까지의 최대공통부분문자열(res)보다 문자열이 더 길 경우의 가능성만 확인. 예를 들어, res의 길이가 6인 경우, 다음 반복에서도 길이가 6 이상인 부분문자열에 대하여만 비교한다.
                if INP1[pos:pos+unt+1] in INP2 and len(INP1[pos:pos+unt+1]) > len(res) :  # 현재까지의 최대공통부분문자열보다 긴 부분문자열이 발견된 경우 :
                    res = INP1[pos:pos+unt+1] # res(결과)를 갱신한다
    print(len(res))
    print(res)

comm_str()

첫 번째 입력의 각 문자를 돌아가며, 그 문자로 시작하는 문자열이 두 번째 입력에 존재하는지를 확인하는 식으로 만들었습니다. 코드에 설명되어 있듯이, 비교 횟수를 조금 줄이려고 노력했습니다.

결과

INPUT1 : photography
INPUT2 : autograph
7
tograph

INPUT1 : abcd
INPUT2 : efgh
0

def part_str(x):    #입력 받은 문자열에 대하여 부분 문자열 리스트를 만들어 주는 함수
    xx=[]
    for i in range (len(x)):    
        for j in range (i+1):
            temp=[]
            for k in range (j,i+1):
                temp.append(x[k])
            if (len(temp)!=1) and (temp not in xx):
                xx.append(temp)
    return(xx)

a=part_str(str(input('a:')))    # 입력받은 문자열을 부분문자열 리스트로 변환시킴
b=part_str(str(input('b:')))
max,max_common=0,[]

for i in range (len(a)):
    if a[i] in b:               #부분문자열 리스트a를 차례로 체크하여 b에 같은 문자열이 있는지 체크
        if len(a[i])==max:
            max_common.append(a[i])

        if len(a[i])>max:
            max=len(a[i])
            max_common=[]
            max_common.append(a[i])        

print (max)
for i in range (len(max_common[0])):
    print (max_common[0][i],end='')

def lcs(words):
    word = [{w[i:j] for i in range(len(w)) for j in range(i, len(w)+1)} for w in words]
    return max(word[0] & word[1])

if __name__ == '__main__':
    words = 'photography', 'autograph'
    print('{0}\n{1}'.format(len(lcs(words)), lcs(words)))

a = input()
alist = []
for i in range(0,len(a)):
    for j in range(i,len(a)+1):
        alist.append(a[i:j])
b = input()
blist = []
for i in range(0,len(b)):
    for j in range(i,len(b)+1):
        blist.append(b[i:j])
result = [x for x in alist if x in blist]
print(result)
for i in result:
    for j in range(len(result)):
        if len(i) > len(result[j]):
            result[j] = '0'
        else:
            continue
for i in result:
    try:
        int(i)

    except ValueError:
        print(i)

파이썬3입니다.

a = 'photography' 
b = 'autograph' 

partStringA = {a[x:y] for x in range(len(a)) for y in range(x,len(a)+1)}
partStringB = {b[x:y] for x in range(len(b)) for y in range(x,len(b)+1)}
commonString = max(partStringA & partStringB)
print(len(commonString))
print(commonString)

def proportString(s):
    setString = {''}
    for i in range(len(s)):
        for k in range(len(s) + 1):
            setString.add(s[i:i + k])
    return setString


a = input()
b = input()
c = max(proportString(a) & proportString(b))
print(len(c), c)

def stringfind(strings):

  i=1

  for_answer=[]

  while i <=len(strings):

    for j in range(0,len(strings)-i+1,1):

       for_answer.append(strings[j:j+i])

    i+=1

  return for_answer

def find_string(a,b):

  for_answer=[]

  for i in a:

    if i in b:

      for_answer.append(i)

  for_answer.sort()

  print(len(for_answer[-1]))

  print(for_answer[-1])

def main():

  word1=input("write your word")

  word2=input("write your word")

  find_string(stringfind(word1),stringfind(word2))

main()

def Same(a,d):
    q=len(d)
    b=len(a) 
    c=[]
    e=[]
    for i in range(b):
        c.append(a[i])    
        c.append(a[i:]) 
        c.append(a[i:b//2])    
        c.append(a[i:-1])

    for i in range(q):
        e.append(d[i])
        e.append(d[i:])
        e.append(d[i:q//2])
        e.append(d[i:-1])
    print(len(max(list((set(e) & set(c))))))
    print(max(list((set(e) & set(c)))))


Same("photography","autograph")

def partial(text):
    result = []
    for i in range(len(text)):
        for j in range(len(text)):
            _temp = text[i:len(text)-j]
            if _temp not in result:
                result.append(_temp)
    result.sort(key=len)
    return result

def common(text1, text2):
    result = []
    list_1 = partial(text1)
    list_2 = partial(text2)
    for member in list_1:
        if member in list_2:
            result.append(member)
    result.sort(key=len)
    print(len(result[-1]), result[-1])

common('photography', 'autograph')

a = 'photography'
b = 'autograph'

def part(x:str):
    result = set([''])
    for i in range(len(x)):
        for j in range(len(x)+1):
            if i<j:
                result.add(x[i:j])
    return result

com = part(a) & part(b)
l = 0
w = ''
for word in com:
    if len(word) > l:
        l = len(word)
        w = word

print(l, w)

def w_product(a) :
    s = set()
    for x in range(len(a)+1):
        for y in range(len(a)+1):
            s.add(a[x:y])
    return s
a = 'photography'
b = 'autograph'

overlap = max(w_product(a) & w_product(b))

print(f'{len(overlap)}\n{overlap}')

#codingdojing_other_LCS_re
#짧은 문자를 큰 순서대로 자른다. 
#각 부분문자가 긴 문자에 포함되는지 확인한다.

a = input()
b = input()

if len(a) >= len(b): M, L = a, b
else: M, L = b, a


r_dic = {}
flag = False

for i in range(len(M), 0, -1): # 6 5 4 3 2 1 / 4인경우
    for j in range(len(M)-i+1): # 6-4 / 0 1 2
        if M[j:j+i] in L:
            r_dic.setdefault(i, [])     #딕셔너리의 값을 리스트 형식으로
            r_dic[i].append(M[j:j+i])

print(max(r_dic))
print(r_dic[max(r_dic)])

처음에는 큰 부분서열부터 비교해서 일치하는 경우가 있으면 break 하려고 했으나, 여러개인 경우도 있을 것 같아 전체를 다 비교하게 바꾸었습니다.

a=input("첫번째 문자열을 입력해주세요")
b=input("두번째 문자열을 입력해주세요")

def solution (str1,str2):
    arr=[]
    if len(str1) >= len(str2):
        b = str1
        a = str2
    else:
        b = str2
        a = str1
    for k in range(len(b)-1):
        for i in range(k+1,len(b)):
            if b[k:i] in a :
                arr.append(b[k:i])
    arr.sort(key=len,reverse=True)
    return  print(len(arr[0]),"\n",arr[0])

solution(a,b)

// Rust

// 두 문자열 중 작은 길이를 substring의 최대 길이로 시작,

// 첫 번째 문자열의 substring 길이를 하나씩 줄여가며, 두 번째 문자열에 포함되어 있는지 확인

// string slice 두 개를 입력값으로 받으므로, reference(&)의 generic lifetime('a)을 사용해야 합니다.

fn common_str<'a>(s1: &'a str, s2: &'a str) -> &'a str {

let mut l = s1.len();
l = l.min(s2.len());            //두 문자열 중 작은 길이

for i in (1..=l).rev() {        //i 부분문자열 길이(l~1)
    for j in 0..=(s1.len()-i) {     //j 시작 인덱스 0 ~ s1.len()-i
        let substr = &s1[j..j+i];   //최대 j+i-1 => s1.len()-1
        if s2.contains(substr) { 
            return substr;
        }
    }
}
""

}

[test]

fn test1() {

assert_eq!(common_str("photography", "autograph"), "tograph");

}

def subset(a):
    length = len(a)
    sub = []

    for i in range(length):
        for j in range(length-i):
            sub.append(a[i:i+j+1])

    return(sub)

a = subset('photography')
b = subset('autograph')
c = list(set(a) & set(b))

for i in range(len(c)-1):
    if len(c[i]) > len(c[i+1]):
        c[i], c[i+1] = c[i+1], c[i]

print(len(c[-1]))
print(c[-1])

# 문제에서 nice는 n i c e ni ic ce nic nice 이렇게 되있음. <- ice가 누락된것 처럼 보임. 그래서 그냥 둘다 진행
s1 = 'photography'
s2 = 'autograph'

# 문제의 예시 'nice'에 맞춘 경우
def ASDF(s):
    Set = {i for i in s}|{''}
    for x in range(1,len(s)):
        for y in range(1,len(s)):
            if x * y + 1 <= len(s):
                Set.add(s[x*(y-1):x*y+1])
    return Set

print(len(max(ASDF(s1) & ASDF(s2))))
print(max(ASDF(s1) & ASDF(s2)))

# 출력결과에 맞춘 경우
def ASDFG(s):
    Set = set([])
    for x in range(0,len(s)+1):
        for y in range(1,len(s)+1):
            Set.add(s[x:y])
    return Set

print(len(max(ASDFG(s1) & ASDFG(s2))))
print(max(ASDFG(s1) & ASDFG(s2)))