Submission #94341

#TimeUsernameProblemLanguageResultExecution timeMemory
94341zeyad49Savez (COCI15_savez)Java
120 / 120
530 ms51812 KiB
/* * for each string, let dp[i] = the maximum length of a subsequence ending at i, for a string s * we know that s will extend on a prefix of s, so let us search for all prefixes of s, and if the prefix matches the suffix * we say that we can extend i to the dp of the prefix, and we implement this efficiently using hashing */ import java.io.*; import java.util.*; class savez { static int n; static int MOD = (int) 1e9 + 9, p = 31, maxN = (int) 2e6 + 5;; public static void main(String[] args) throws IOException { Scanner sc = new Scanner(); PrintWriter out = new PrintWriter(System.out); n = sc.nextInt(); int ans = 1; HashMap<Integer, Integer> map = new HashMap(); for (int i = 0; i < n; i++) { char[] s = sc.next().toCharArray(); int len = s.length; int[] hash = new int[len]; long pow = 1; long last = 0; for (int j = 0; j < len; j++) { last = last + (s[j] - 'A' + 1) * 1l * pow; last %= MOD; hash[j] = (int) last; pow = pow * p % MOD; } int dp = 1; pow = 1; for (int prefix = len; prefix > 0; prefix--) { int preHash = hash[prefix - 1], sufHash = hash[len - 1] - (prefix == len ? 0 : hash[len - 1 - prefix]); if (sufHash < 0) sufHash += MOD; if (sufHash == (preHash * 1l * pow % MOD)) dp = Math.max(dp, 1 + map.getOrDefault(preHash, 0)); pow = pow * p % MOD; } map.put(hash[len - 1], dp); ans = Math.max(ans, dp); } out.println(ans); out.close(); } static class Scanner { BufferedReader br; StringTokenizer st; Scanner() { br = new BufferedReader(new InputStreamReader(System.in)); } Scanner(String fileName) throws FileNotFoundException { br = new BufferedReader(new FileReader(fileName)); } String next() throws IOException { while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine()); return st.nextToken(); } String nextLine() throws IOException { return br.readLine(); } int nextInt() throws IOException { return Integer.parseInt(next()); } long nextLong() throws NumberFormatException, IOException { return Long.parseLong(next()); } double nextDouble() throws NumberFormatException, IOException { return Double.parseDouble(next()); } } }

Compilation message (stderr)

Note: savez.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...