Submission #980687


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Pavel Mavrin
 */
public class Main {

    private void solve() throws IOException {
        int n = nextInt();
        String S = next();
        String T = next();
        if (S.equals(T)) {
            out.println(0);
            return;
        }
        int j = n - 1;
        int res = 0;
        int[] q = new int[n + 1];
        int h = 0;
        int t = 0;
        int d = 0;
        int jj = n;
        for (int i = n - 1; i >= 0; i--) {
            if (j > i) j = i;
            while (j >= 0 && S.charAt(j) != T.charAt(i)) j--;
            if (j < 0) {
                out.println(-1);
                return;
            }
            while (t > h) {
                int xx = q[h] - d;
                if (xx > i) {
                    h++;
                } else {
                    break;
                }
            }
            if (j < i && j != jj) {
                d++;
                q[t++] = (j + d);
                res = Math.max(res, t - h);
            }
            jj = j;
//            System.out.println(i + " " + j);
//            for (int e = h; e < t; e++) {
//                System.out.println(q[e] - d);
//            }
        }
        out.println(res);
    }

    private BufferedReader br;
    private PrintWriter out;
    private StringTokenizer st;

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    private void run() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

}

Submission Info

Submission Time
Task F - Shik and Copying String
User pashka
Language Java8 (OpenJDK 1.8.0)
Score 1500
Code Size 2219 Byte
Status AC
Exec Time 1675 ms
Memory 28012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1500 / 1500
Status
AC × 4
AC × 63
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt, example3.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt AC 94 ms 8012 KB
001.txt AC 93 ms 8272 KB
002.txt AC 96 ms 8140 KB
003.txt AC 93 ms 8144 KB
004.txt AC 95 ms 8140 KB
005.txt AC 95 ms 8016 KB
006.txt AC 96 ms 8140 KB
007.txt AC 96 ms 8144 KB
008.txt AC 94 ms 8272 KB
009.txt AC 95 ms 8012 KB
010.txt AC 97 ms 8268 KB
011.txt AC 96 ms 8268 KB
012.txt AC 96 ms 8268 KB
013.txt AC 95 ms 8276 KB
014.txt AC 96 ms 8268 KB
015.txt AC 94 ms 8400 KB
016.txt AC 98 ms 8272 KB
017.txt AC 97 ms 8268 KB
018.txt AC 97 ms 8140 KB
019.txt AC 96 ms 8268 KB
020.txt AC 94 ms 8144 KB
021.txt AC 95 ms 8272 KB
022.txt AC 95 ms 8276 KB
023.txt AC 96 ms 8268 KB
024.txt AC 95 ms 8276 KB
025.txt AC 202 ms 22388 KB
026.txt AC 230 ms 27196 KB
027.txt AC 248 ms 27092 KB
028.txt AC 227 ms 27200 KB
029.txt AC 240 ms 27144 KB
030.txt AC 216 ms 27068 KB
031.txt AC 227 ms 27096 KB
032.txt AC 210 ms 27040 KB
033.txt AC 220 ms 27068 KB
034.txt AC 222 ms 26968 KB
035.txt AC 225 ms 27180 KB
036.txt AC 231 ms 27648 KB
037.txt AC 237 ms 27168 KB
038.txt AC 223 ms 27184 KB
039.txt AC 220 ms 27200 KB
040.txt AC 242 ms 27124 KB
041.txt AC 227 ms 27076 KB
042.txt AC 231 ms 27124 KB
043.txt AC 1675 ms 27788 KB
044.txt AC 229 ms 27068 KB
045.txt AC 238 ms 27052 KB
046.txt AC 241 ms 27608 KB
047.txt AC 239 ms 27068 KB
048.txt AC 279 ms 27068 KB
049.txt AC 259 ms 27056 KB
050.txt AC 236 ms 27608 KB
051.txt AC 231 ms 27076 KB
052.txt AC 238 ms 27216 KB
053.txt AC 241 ms 27624 KB
054.txt AC 248 ms 28012 KB
055.txt AC 238 ms 27060 KB
056.txt AC 222 ms 27068 KB
057.txt AC 244 ms 26940 KB
058.txt AC 230 ms 27064 KB
example0.txt AC 94 ms 8144 KB
example1.txt AC 95 ms 8140 KB
example2.txt AC 137 ms 8144 KB
example3.txt AC 93 ms 8144 KB