[ACM] Problem B. Editor
Posted 2008/07/12 16:27어떤 문자열이 존재한다. 이 안에서 2번 이상 존재하는 부분 문자열 중에 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다. 두 문자열은 겹칠 수 있다.
대회 당시 풀었던 방식을 회상해보았다. 모든 부분 문자열을 생성하여 String의 indexOf method와 lastIndexOf method를 사용하여 이 문제를 해결했었는데 별로 효율적인 방법이 아닌 것 같아 외부 사이트의 도움을 받아보기로 하였다.
이 문제를 풀기 위해서 알고스팟의 도움을 받았다. (http://algospot.com/zbxe/icpc/5108)
알고스팟의 풀이방식을 보니 어느정도 c 스타일의 문제풀이 습관을 길러야 겠다는 생각이 들었다. 이 중에서 2가지 방법으로 문제를 해결해 보았다.
1. 일반적인 방법
이 방법은 모든 a, b위치에 대해서 a부터 시작하는 prefix와 b부터 시작하는 prefix의 공통 길이를 매번 구해 최대값을 구하는 방법이다.
import java.util.Scanner;
public class B_1 {
Scanner in = new Scanner(System.in);
String word;
public B_1() {
int n = in.nextInt();
for(int i=0 ; i<n ; ++i) {
start();
}
}
public void start() {
int max = 0;
word = in.next();
for(int i=0 ; i<word.length() ; ++i)
for(int j=i+1 ; j<word.length() ; ++j)
max = Math.max(max, getCommonLength(i, j));
System.out.println(max);
}
public int getCommonLength(int a, int b) {
int len = 0;
while(a+len<word.length() &&
b+len<word.length() &&
word.charAt(a+len)==word.charAt(b+len))
++len;
return len;
}
public static void main(String[] args) {
new B_1();
}
}
public class B_1 {
Scanner in = new Scanner(System.in);
String word;
public B_1() {
int n = in.nextInt();
for(int i=0 ; i<n ; ++i) {
start();
}
}
public void start() {
int max = 0;
word = in.next();
for(int i=0 ; i<word.length() ; ++i)
for(int j=i+1 ; j<word.length() ; ++j)
max = Math.max(max, getCommonLength(i, j));
System.out.println(max);
}
public int getCommonLength(int a, int b) {
int len = 0;
while(a+len<word.length() &&
b+len<word.length() &&
word.charAt(a+len)==word.charAt(b+len))
++len;
return len;
}
public static void main(String[] args) {
new B_1();
}
}
2. Suffix Array를 사용하는 방법
이 방법은 입력받은 String의 Suffix Array를 구성하여 정렬한다. 그 후에 인접한 두 Suffix들을 비교하여 최대 길이를 구하는 방법이다.
import java.util.*;
public class B_2 {
Scanner in = new Scanner(System.in);
String word;
String[] suffixesOfWord;
public B_2() {
int n = in.nextInt();
for(int i=0 ; i<n ; ++i) {
start();
}
}
public void start() {
int maxLength = 0;
word = in.next();
makeSuffixArray();
Arrays.sort(suffixesOfWord);
for(int i=0 ; i<suffixesOfWord.length-1 ; ++i) {
maxLength = Math.max(maxLength, getCommonLength(i));
}
System.out.println(maxLength);
}
private int getCommonLength(int index) {
int i=0;
for(i=0 ; i<suffixesOfWord[index].length() && i<suffixesOfWord[index+1].length() ; ++i) {
if(suffixesOfWord[index].charAt(i) != suffixesOfWord[index+1].charAt(i))
break;
}
return i;
}
private void makeSuffixArray() {
suffixesOfWord = new String[word.length()];
for(int i=word.length()-1 ; i>=0 ; --i)
suffixesOfWord[i] = word.substring(i);
}
public static void main(String[] args) {
new B_2();
}
}
public class B_2 {
Scanner in = new Scanner(System.in);
String word;
String[] suffixesOfWord;
public B_2() {
int n = in.nextInt();
for(int i=0 ; i<n ; ++i) {
start();
}
}
public void start() {
int maxLength = 0;
word = in.next();
makeSuffixArray();
Arrays.sort(suffixesOfWord);
for(int i=0 ; i<suffixesOfWord.length-1 ; ++i) {
maxLength = Math.max(maxLength, getCommonLength(i));
}
System.out.println(maxLength);
}
private int getCommonLength(int index) {
int i=0;
for(i=0 ; i<suffixesOfWord[index].length() && i<suffixesOfWord[index+1].length() ; ++i) {
if(suffixesOfWord[index].charAt(i) != suffixesOfWord[index+1].charAt(i))
break;
}
return i;
}
private void makeSuffixArray() {
suffixesOfWord = new String[word.length()];
for(int i=word.length()-1 ; i>=0 ; --i)
suffixesOfWord[i] = word.substring(i);
}
public static void main(String[] args) {
new B_2();
}
}
이올린에 북마크하기'C.S.E > Algorithm' 카테고리의 다른 글
| [PKU] 1003 Hangover (0) | 2008/07/23 |
|---|---|
| PKU Judge Online 소개 (0) | 2008/07/23 |
| [ACM] Problem B. Editor (0) | 2008/07/12 |
| [ACM] 2007 Problem A - Molar mass (0) | 2008/07/09 |
| [IBM Developer Works]초보개발자 코드 트레이닝 Part 2. (0) | 2008/05/16 |
| [UVA] 10198 Counting (0) | 2008/05/06 |
- Filed under : C.S.E/Algorithm
- Tag : ACM, Algorithm
- Comment Trackback
