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 |
|
|
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 |