백준 21592번 Longest Common String JAVA 구현해보기

---

```

백준 21592번 Longest Common String JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 21592번 풀이
2.  두 문자 열간 가장 긴 공통 문자열 찾기
3.  n개의 문자열간 가장 긴 공통 문자열 찾기

---

https://www.acmicpc.net/problem/21592

21592번: Longest Common Substring

 

 

 

백준 21592번 Longest Common String 은 

난이도 실버 등급의 문제로서

 

N개의 문자열이 주어질 때

가장 긴 공통문자열을 찾으면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

두 개의 문자열의 가장 큰 공통 문자열

 

첫 생각은 두 개의 문자열의 공통으로 긴 문자열을 찾고

재귀적으로 찾아나가는 것이었으나

abcdefg

abckefg처럼

두문자 열이 두 개 이상의 공통으로 긴 문자열을 가지는 경우 계산이 힘들기 때문에 패스하였습니다.

 

////////////////////////////////////////////////////////////////
// 첫시도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    
    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String k = "axabcrwmvd";
        String ak = "zzzzzzzazzzzz";
        System.out.println(findLCS(k, ak));
    }

    // find the longest common substring
    private static String findLCS(String str1, String str2) {

        final int str1Len = str1.length();
        final int str2Len = str2.length();

        int dp[][] = new int[2][str2Len+1];
        int commonStrLen = 0;
        String commonStr = "";

        for(int i=1;i<=str1Len;i++)
        {
            for(int j=1;j<=str2Len;j++)
            {
                if(str1.charAt(i-1)==str2.charAt(j-1))
                {
                    dp[i%2][j]=dp[(i-1)%2][j-1]+1;
                    if(dp[i%2][j]>commonStrLen){
                        commonStrLen=dp[i%2][j];
                        commonStr += str1.charAt(i-1);
                    }

                }
                else dp[i%2][j]=0;
            }
        }

        return commonStr;
    }
}

////////////////////////////////////////////////////////////////

---

N개의 문자열의 가장 큰 공통 문자열

 

두 번째 방법은 문자열들을 정렬해준 다음

가장 짧은 문자열을 기준으로

brute force 방식으로 가장 긴 공통 문자열을 구해주는 방법입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력
        // String 을 List 에 넣어준다.
        int numOfStr = Integer.parseInt(br.readLine());
        List<String> stringList = new ArrayList<>();

        for (int i = 0; i < numOfStr; i++) {
            stringList.add(br.readLine());
        }

        // Size별로 Sort해준다.
        stringList.sort(Comparator.comparing(String::length));

        final String firstElem = stringList.get(0);
        final int firstElemLength = firstElem.length();
        String lCStr = "";

        for (int i = 0; i < firstElemLength; i++) {
            for (int j = i + 1; j <= firstElemLength; j++) {
                final String tempStr = firstElem.substring(i, j);

                int k = 1;
                for (k = 1; k < numOfStr; k++) {
                    if (!stringList.get(k).contains(tempStr)) {
                        break;
                    }
                }

                if ((k == numOfStr) && (lCStr.length() < tempStr.length())) {
                    lCStr = tempStr;
                }

            }
        }

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

 

다행히도 두 번째 방법으로 통과하였습니다.

 

 

참조

https://stackoverflow.com/questions/17150311/java-implementation-for-longest-common-substring-of-n-strings

Java implementation for longest common substring of n strings

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---