중복되는 가장 긴~ 문자열 찾기 알고리즘(2)

문자열 S를 함수에 집어 넣으면 중복되는 부분문자 중에 가장 긴 부분문자를 리턴해라

ex) aaabcabcab => aaabcabcab =aaabcabcab 다음과 같이 가장 길은 부분문자열은 abcab이다

[출처] 2009/10/17 Daum C

oding Test |작성자 JunSu

import java.util.Hashtable;

import java.util.Vector;

public class test3 {

public static void main(String[] args) {

String str = "aaabcabcab";//연산할 문자열

Vector<String> v = new Vector<String>(); //겹치지 않는 부분문자 벡터집합

Vector<String> v2 = new Vector<String>();//2개이상 똑같은 부분문자 벡터집합

Hashtable<String, Integer> h = new Hashtable<String, Integer>();//벡터 v에 들어가는 문자열들의  갯수가 들어갈 해쉬테이블

//연산할 문자열을 조각으로 나누어 최소 하나 이상의 문자만 찾아 벡터 v 와 해쉬테이블 h 에 넣는다.

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

for (int j = i; j < str.length(); j++) {

String tempstr = str.substring(i,j+1); 

boolean tf = false;

for (int k = 0; k < v.size(); k++) {

String vstr = (String) v.get(k);

if(vstr.equals(tempstr)){//겹치는 문자가 있다면

tf = true;

int inth = h.get(tempstr);

h.put(tempstr, inth+1);//겹치는문자가 있기에 카운트를 하나 올려준다

}

}

if(tf == false){//겹치는 문자가 없으므로 벡터와 해쉬테이블에 새롭게 집어넣는다

v.add(tempstr);

h.put(tempstr, 1);

}

}

}

int maxlength = 2; //최소문자길이가 2개 이상만 걸러내기위한 초기값

//해쉬테이블에서 카운트가 2개 이상인 문자열 만 벡터 v2에 넣는다.

//또한 v2에 들어가는 문자열중 가장 긴 길이의 문자열을 찾는다.

// 가장 긴 문자열의 길이는 maxlength에 넣는다.

for (int i = 0; i < v.size(); i++) {

//System.out.println(v.get(i) + " : " + h.get(v.get(i)));

if(h.get(v.get(i)) >= 2){

v2.add(v.get(i));

if(v.get(i).length() > maxlength){

maxlength = v.get(i).length();

}

}

}

//maxlength와 같은 길이의 문자열만 출력한다.(2개이상일수 있다.)

for (int i = 0; i < v2.size(); i++) {

if(v2.get(i).length() == maxlength){

System.out.println(v2.get(i));

}

}

String str = "aaabcabcab";

String str_temp = "";

int  max = 1; //최대 문자열의 길이 

/**

* aaabcabcab의 문자열에서 aa를 비교할경우 첫 문자 a를 제외한 aabcabcab 에서 비교한다.

* 비교할 첫 문자만 자르고 비교하면 해당 문자열에선 같은 문자가 비교에 의해서만 확인가능하다.

* i를 증가시키며 첫문자열만을 빼면서 하나씩 비교한다.

* 이는 문자열의 중복은 앞에 있다면 당연히 뒤에 있을 수밖에 없으며

* 뒤에서 자른 문자열은 원본의 앞 문자열과 비교할 필요가 없다는 것을 뜻한다.

* (있었다면 벌써 앞에서 비교가 있었다.)

* 이에 j를 i 시작점에서 증가 시켜서 차례대로 비교하고 최대 문자열의 길이만 판독하면 된다.

* 

*/

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

for (int j = i; j < str.length(); j++) {

String str_div = str.substring(i, j+1); //문자열의 처음부터 차례대로 잘라나감.

String str_div2 = str.substring(i+1);   //자른 문자열의 첫문자만 빼고 자름.

//System.out.println(str_div2.matches(".*"+str_div+".*") + "  " + str_div + " " + str_div2);

//문자열 비교.

if(str_div2.matches(".*"+str_div+".*"))

//계산값중 가장 긴 문자열 이며 , 원본과 다를때.

if((max < str_div.length())&& (str_div.length() != str.length())){

max = str_div.length();

str_temp = str_div;

//System.out.println(str_temp);

}

}

}

  System.out.println(max + "  " + str_temp);

  

}

}

-_- 흠..의외로..간단하네..

정말 간단했는데..-_- 그동안 그지 같이 풀었었구나.. 이러니 떨어질만 하지.. 

10줄이면 끝나는걸.. 벡터에 해쉬에..미친칫을 했구나…'

보는 사람들이 얼마나 병신같다고 생각했을까..-0-;; 겁나 부끄러워지네..