[LPS] (Longest Prefic which is also Suffix)

개념

LPS : 주어진 문자열의 가장 긴 접두어이자 접미어.

    즉, 주어진 문자열 내에서 구할수 있는 부분집합 중, 앞에서부터 가장 긴 부분집합 또는 뒤에서부터 가장 긴 부분집합

prefix (접두어) : 문자열의 0번 인덱스부터 시작하는 모든 부분집합

suffix (접미어) : 문자열의 마지막 인덱스부터 시작하는 모든 부분집합 (단, 부분집합 내 인자 순서는 앞에서부터 진행)

non-overlapping : 접두어와 접미어는 서로 겹치는 인덱스가 없어야 한다.

---

문제

임의의 문자열을 입력받아, non-overlapping 조건을 만족하는 LPS의 길이를 구하시오

---

원리

예를들어, "abccab"가 주어질 경우, 

prefix	a, ab, abc, abcc, abcca, abccab
suffix	b, ab, cab, ccab, bccab, abccab
LPS   (접두어==접미어인 경우)	ab
non-overlapping 조건 없는 경우	abccab

 

부분 문자열 구하는 문법

str.substring(시작인덱스, 끝나는 인덱스보다 +1인 인덱스)

예를 들어 str = "abccab" 일 때, str.substring( 0, str.length()/2 ) = "abc"

                str = "abccab" 일 때, str.substring( str.length()/2, str.length() ) = "cab"

예를 들어 str = "abcfcab" 일 때, str.substring( 0, str.length()/2 ) = "abc"

                str = "abcfcab" 일 때, str.substring( str.length()/2, str.length() ) = "fcab"

---

나의 코드

방법 1 : 접두어와 접미어를 모두 모아 비교하는 방법

import java.util.*;

public class lps {
	public static int LPS (String str) {
        /*
        1. 주어진 문자열을 반으로 나눈다
        2. 반쪽짜리 앞에서 prefix를 반쪽짜리 뒤에서 suffix를 arraylist로 구한다
        3. 두 arraylist를 비교해서 같고, 해당 요소의 길이가 max보다 크면, 길이를 max에 할당
        4. max return
         */

        // 문자열 준비 ------------------------------------------
        String front = "";
        String back = "";

        if (str.length()%2==1) { // str의 길이가 홀수일 때,
            front = str.substring(0, str.length()/2);
            back = str.substring(str.length()/2+1,str.length());
        }
        else if(str.length()%2==0) { // str의 길이가 짝수일 때,
            front = str.substring(0, str.length()/2);
            back = str.substring(str.length()/2, str.length());
        }

        // 조건 만들기 ------------------------------------------
        ArrayList<String> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();
        String temp1 = "";
        String temp2 = "";
        int max = 0;

        for (int i=0 ; i<front.length() ; i++) {
            temp1 += front.charAt(i);
            list1.add(temp1);
        }

        for (int i=back.length()-1 ; i>=0 ; i--) {
            temp2 = back.charAt(i) + temp2;
            list2.add(temp2);
        }

        for (int j=0 ; j < list1.size() ; j++) {
            if(list1.get(j).equals(list2.get(j)) && max<=list1.get(j).length()) {
                max = list1.get(j).length();
            }
        }

        return max;
    }
}

---

방법 2 : 접두어와 접미어 만드는 과정에서 비교하기

import java.util.*;

public class lps {
    public static void main(String[] args) {
        // 문자열 준비 ------------------------------------------
        String front = "";
        String back = "";

        if (str.length()%2==1) { // str의 길이가 홀수일 때,
            front = str.substring(0, str.length()/2);
            back = str.substring(str.length()/2+1,str.length());
        }
        else if(str.length()%2==0) { // str의 길이가 짝수일 때,
            front = str.substring(0, str.length()/2);
            back = str.substring(str.length()/2, str.length());
        }
        
        // 조건 만들기 ------------------------------------------
        String temp1 = "";
        String temp2 = "";
        int max = 0;

        for (int i = 0; i < front.length(); i++) {
            temp1 += front.charAt(i);
            temp2 = back.charAt(front.length()-1-i) + temp2;
            if (temp1.equals(temp2) && max <= temp1.length()) max = temp1.length();
        }

        return max;
    }
}

---

레퍼런스 코드

public class reference {
    public int LPS(String str) {
        if (str.length() < 2) return 0;

        int leftIdx = 0;
        int rightIdx = (str.length() / 2);

        while (rightIdx < str.length()) {
            if (str.charAt(leftIdx) == str.charAt(rightIdx)) {
                leftIdx++;
                rightIdx++;
            } else {
                rightIdx = rightIdx - leftIdx + 1;
                leftIdx = 0;
            }
        }
        return leftIdx;
    }
}

---

참고 링크 

나의 깃 링크 : https://github.com/PNUHCT/AlgorismStorage.git

멱집합 : https://radpro.tistory.com/257

LPS : https://gusdnd852.tistory.com/172