가장 긴 공통의 부분문자열 구하기

여기서의 “부분”은 LCS문제에서의 “부분”과는 다른 의미임을 명심하라. nice라는 문자열이 있다면 이 문제에서의 부분문자열의 집합은 {‘’, n, i, c, e, ni, ic, ce, nic, nice}이다.

LCS문제에서의 “부분”에서는 nce도 하나의 부분문자열로 볼 수 있지만 이 문제에서는 부분문자열이 아니다. (즉, 이 문제에서의 “부분”은 원래 문자열에서 일정 부분을 잘라낸 것이다.)

photography와 autograph 두 문자열이 있다고 할 때, ph, grap, to 등의 부분문자열이 있으며, 이 중 최대의 길이를 갖는 부분문자열은 tograph이다.

입력

두 줄에 각각의 스트링이 주어진다. 각 스트링의 길이는 4000이하이다.

photography
autograph

출력

첫줄에 찾은 부분문자열의 길이, 둘째 줄에 가장 긴 공통의 부분문자열을 출력한다.

7
tograph
  • 파일 입출력 방식으로 하지 않습니다.
  • 문제출처 : 컴퓨터 알고리즘 (홍릉과학출판사) 314p
최적해 구하기 알고리즘
이 문제는 병렬연산으로 해결하기 좋아보이는데요~ 혹시 병렬처리로 이문제 해결하신분 없나요?ㅎ - 윤태호, 2016/09/21 09:47 M D
병렬 연산으로 해결해야 할 만큼 연산량이 많지 않아서... 잘은 모르겠는데 파이썬의 경우에는 프로세스 생성하는데 시간이 더 걸립니다. 물론 몇백개라면 나누어서 할 수도 있겠지만요.... - Flair Sizz, 2016/10/02 23:53 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

22개의 풀이가 있습니다. 1 / 3 Page

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
독해 불가 @_@;; - 이 종성, 2016/09/10 14:22 M D
보고 또보고 또보니 조금 이해가 되네요, 휴우~ 루비는 심오한 언어군요, - 이 종성, 2016/09/10 14:35 M D
루비를 연습하느라 가독성이 떨어지게 작성되었네요. 리스트 조작(map, sort_by, reduce, max_by) 표현을 사용했습니다. 파이썬을 비롯해 여러 언어들이 이와같은 표현을 갖고 있습니다. 금방 익숙해지는 표현인데 처음엔 어렵더라구요. 마틴 파울러의 '컬렉션 파이프라인' 글( http://martinfowler.com/articles/collection-pipeline/ )에 개념설명, 장단점이 잘 설명되어 있습니다. 루비는 스트레스가 없는 프로그래밍을 지향합니다. 손에 달라붙는 즐거운 언어라 추천드리고 싶네요. python, clojure, haskell도 멋지다고 생각합니다. - 권용훈, 2016/09/10 18:49 M D
보내주신 글을 읽고 제가 주로쓰는 c#언어에서도 lamda가 있는것을 알고, c#으로 최대한 비슷하게 만들어 보면서 의미를 해석해 봤습니다. reduce와 똑같은 함수를 c#에서는 못찾겠네요. 대신 급한데로 select를 사용하여 보았네요, 공부를 하니 소스가 잘보이네요, 설명글도 무슨 이야기 인지 잘보이고요. 재밌게 공부하보았슴다. 매력이 있네요. 아직 재밌고 흥미롭다 이외에 왜 좋은가 장점 같은 것은 잘모르겠네요, 좀 알려 주면 안될지, 보내주신 글에는 한번 알게되면 없으면 못살거라는 정도로 말하고 넘어가는듯 하고... - 이 종성, 2016/09/10 21:53 M D
1. (1..10).select(&:짝수?).map(&문자열로결합) 처럼 하나하나 분리된 명령을 조합할 수 있고, 왼쪽에서 오른쪽으로 평문 읽듯이 코드를 읽고 작성해나갈 수 있다는 장점이 있습니다. 압축된 표현도 가능하구요. 2. lazy 적용에 유용. 보통은 구문 전부를 한번에 평가하게 됩니다. 가령, (1..무한대).select(짝수)처럼 구문을 사용하면 (1..무한대)에서 프로그램은 멈추고 말죠. (1..무한대).lazy.select(짝수).take(5)처럼 lazy를 적용하게 되면 가장앞부터 구문끝까지 1만 통과시키고 2를 통과시키고 이렇게 반복을 하게 됩니다. 만족하는 결과 5개를 얻을 때 까지요. 따라서 대용량 자료의 순차적인 처리나 계산중인 결과물을 바로바로 획득할 때 빠르고 편합니다.(요 아래 개미수열 문제가 lazy문제입니다) 3. 병렬성. 처리할 내용 각각을 멀티코어나 쓰레드로 처리할 수도 있죠. 가령 jobs = 뉴스사이트10개.map {|i| future { 사이트읽어오기 }; Concurrent.zip(*jobs) 처럼 하면 비동기로 10개요청을 쏘고 10개가 다들어오면 결과를 출력하는 구문이 됩니다. 간단하고 쉽고 보기좋죠. 4. 불변성 : 데이터를 여러번 이리저리 조작하게 되므로 쓰레드에 안전하고 side-effect에 강건하기 위해서는 불변 자료구조의 필요성을 느끼고 추구하게됩니다. 한번 수행하고 나서 두번째 수행하는데 기대한 결과물이 나오지 않는다? 이런경우를 접하게 되거든요. 불변자료구조를 추구하는건 좋은 방향이구요. 불변자료구조를 취하지 않더라도 구문을 쪼개고 조작하다보면 side-effect가 어디서 발생하는지 왜 문제가되는지, 어떻게 회피해야하는지를 조금씩 인식하게 됩니다. 5. 디버깅 : 1개의 구문이 여러개의 절로 분리되는데.. 한개의 절은 한가지 목적으로 입출력을 기대하게 되는데 그것만 체크하면 되니 아무래도 디버깅이 쉬워지겠죠. - 어디에 사용해야하나? : 특별하다기 보다 표현법의 하나니 for문 case, if~else처럼 써도 상관없습니다. 단점도 물론 있습니다. 가변성 객체를 다루거나 함수 바깥에서 변하는 값을 사용하는 경우 작성, 디버깅, 가독성 모두 좋지 않습니다. 제가 위에 작성한 코드도 그와같은 면에선 좋지 않은 코드구요(짧게 작성하면서 구문을 이리저리 트는걸 연습하는 중이라..). - 더 깊게 알아보기 : 아는 한도내에서 쉽게 설명하려고 했는데 전문가가 아니라 설명이 취약합니다. 함수형 프로그래밍, list comprehension에 대해서 쉽게 쓰여진 글들을 살펴보시면 좋을 것 같습니다. 전엔 특별한 구문이나 기법처럼 여겨졌지만 지금은 일반화된 유용한 표현법으로 취급되니 알아두면 필요할 때 깔끔하고 응축된 좋은 코드를 작성하실 수 있지 않을까 싶습니다. - 권용훈, 2016/09/10 22:56 M D
아, 아주 정성들여 답변을 작성해 주셨네요, 저도 열심히 정독했습니다. 일부러 ruby의 함수형 언어 기법을 연구하고 익숙해 지기 위해서 코딩도장에서 예제를 풀어보면서 연마 중이시군요, 재밌는 영역이네요. 마틴파울러글에 이미 말씀주신 장점들이 다 적혀 있었군요, 밑에 까지 읽었어야하는데 윗부분만 읽어서 글이 너무 길더라구요.. 민망합니다. 일반적으로 많이 사용하는 부분이니 눈으로 보고 익혀 둬야 겠네요. 고맙습니다. - 이 종성, 2016/09/11 00:51 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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);
    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

최적해 구하기 x 1
알고리즘 x 1

언어별 풀이 현황
전 체 x 22
java x 2
기 타 x 5
python x 7
javascript x 1
cpp x 2
haskell x 1
cs x 2
php x 1
ruby x 1