2774 - Memory Limit Exceeded 2012/09/28

• 2774 -- Long Long Message

Memory Limit Exceeded
Memory超過でfailed

考え方はまちがってないと思うんだけど...

まちがってるな... とりあえずおいておこう。。。
通らないけど、動作としては問題ないかな....

package p2774_suffixarray;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    static class A implements Comparable {
        String s;
        int marker;

        public A(String s, int marker) {
            this.s = s;
            this.marker = marker;
        }

        @Override
        public int compareTo(Object o) {
            return s.compareTo(((A) o).s);
        }

        public String toString() {
            return s + ":" + marker;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line1 = scanner.nextLine();
        String line2 = scanner.nextLine();
        char[] cs1 = line1.toCharArray();
        char[] cs2 = line2.toCharArray();
        ArrayList<A> list = new ArrayList<Main.A>();

        for (int i = 0; i < cs1.length; i++) {
            char[] cs = new char[cs1.length - i];
            System.arraycopy(cs1, i, cs, 0, cs.length);
            list.add(new A(new String(cs), 0));
        }

        for (int i = 0; i < cs2.length; i++) {
            char[] cs = new char[cs2.length - i];
            System.arraycopy(cs2, i, cs, 0, cs.length);
            list.add(new A(new String(cs), 1));
        }

        int max = 0;
        Collections.sort(list);

        // for (A a : list) {
        // System.out.println(a);
        // }
        for (int i = 1; i < list.size(); i++) {
            A a1 = list.get(i - 1);
            A a2 = list.get(i);
            if (a1.marker == a2.marker)
                continue;
            int n = LCP(a1.s, a2.s);
            max = max < n ? n : max;

        }
        System.out.println(max);
    }

    static int LCP(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int len1 = s1.length();
        int len2 = s2.length();
        int min = len1 < len2 ? len1 : len2;
        int ret = 0;
        for (int i = 0; i < min; i++) {
            if (cs1[i] != cs2[i])
                break;
            ret++;
        }

        return ret;
    }
}

mapでってやってぜんぜんだめなやつ

import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line1 = scanner.nextLine();
        String line2 = scanner.nextLine();
        char[] cs1 = line1.toCharArray();
        char[] cs2 = line2.toCharArray();
        Map<String,Integer> set1 = new TreeMap<String, Integer>();
        for(int i=0;i<cs1.length;i++){
            char[] cs = new char[cs1.length - i];
            System.arraycopy(cs1, i, cs, 0, cs.length);
            set1.put(new String(cs), 0);
        }

        for(int i=0;i<cs2.length;i++){
            char[] cs = new char[cs2.length - i];
            System.arraycopy(cs2, i, cs, 0, cs.length);
            set1.put(new String(cs), 1);
        }
          
        int max = 0;
        Entry<String, Integer> tmp = null;
        for (Entry<String, Integer> set: set1.entrySet()) {
            if(tmp == null){
                tmp = set;
                continue;
            }
            if(tmp.getValue() == set.getValue()) continue;
            int n = LCP(tmp.getKey(),set.getKey());
            max = max < n ? n:max;
            tmp = set;
        }
      
        System.out.println(max);
    }

    static int LCP(String s1, String s2){
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int len1 = s1.length();
        int len2 = s2.length();
        int min = len1 < len2 ? len1:len2;
        int ret = 0;
        for(int i=0;i<min;i++){
            if(cs1[i] != cs2[i]) break;
             ret++;
        }
      
        return ret;
    }
}