oj.uz

답안 #583587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583587 2022-06-25T16:26:22 Z DylanSmith 원형 문자열 (IZhO13_rowords) Java 11
24 / 100
 246 ms 33376 KB 
import java.util.*;
import java.io.*;
public class rowords {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        String s1 = in.next(), s2 = in.next();
        int res = Math.min(lis(s1 + s1, s2), lis(s1, s2 + s2));
        out.println(res);
        
        out.close();
    }
    public static int lis(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 11136 KB Output isn't correct
2 Correct 167 ms 10508 KB Output is correct
3 Correct 155 ms 10672 KB Output is correct
4 Correct 155 ms 10556 KB Output is correct
5 Incorrect 165 ms 10664 KB Output isn't correct
6 Correct 192 ms 13232 KB Output is correct
7 Correct 200 ms 27560 KB Output is correct
8 Incorrect 234 ms 27568 KB Output isn't correct
9 Incorrect 221 ms 27788 KB Output isn't correct
10 Incorrect 216 ms 27720 KB Output isn't correct
11 Incorrect 246 ms 33300 KB Output isn't correct
12 Correct 199 ms 33288 KB Output is correct
13 Incorrect 235 ms 33128 KB Output isn't correct
14 Incorrect 244 ms 33376 KB Output isn't correct
15 Incorrect 238 ms 33272 KB Output isn't correct
16 Incorrect 225 ms 33312 KB Output isn't correct
17 Incorrect 236 ms 19664 KB Output isn't correct
18 Incorrect 235 ms 33180 KB Output isn't correct
19 Incorrect 234 ms 27532 KB Output isn't correct
20 Incorrect 234 ms 32928 KB Output isn't correct
21 Incorrect 213 ms 14080 KB Output isn't correct
22 Incorrect 222 ms 19616 KB Output isn't correct
23 Incorrect 226 ms 19612 KB Output isn't correct
24 Incorrect 238 ms 19776 KB Output isn't correct
25 Incorrect 227 ms 27316 KB Output isn't correct