Submission #729363

#	Time	Username	Problem	Language	Result	Execution time	Memory
729363		rahulverma	Lozinke (COCI17_lozinke)	Java	100 / 100	822 ms	18220 KiB

lozinke

import java.io.*;
import java.util.*;

public class lozinke {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] vals = new String[n];
		for(int i = 0; i < n; i++) vals[i] = br.readLine();
		Arrays.sort(vals, (a, b) -> a.length() - b.length());
		HashMap<String, Integer> occ = new HashMap<String, Integer>();
		int ans = 0;
		for(int i = 0; i < n; i++) {
			if(occ.containsKey(vals[i])) {
				occ.put(vals[i], occ.get(vals[i]) + 1);
			}
			else {
				occ.put(vals[i], 1);
			}
		}
		for(String key: occ.keySet()) {
			if(occ.get(key) > 1) {
				ans += (occ.get(key) * (occ.get(key) - 1));
 			}
		}
		for(int i = 0; i < n; i++) {
			HashSet<String> used = new HashSet<String>();
			for(int j = 0; j < vals[i].length(); j++) {
				for(int k = j; k < vals[i].length(); k++) {
					String sub = vals[i].substring(j, k+1);
					if(occ.containsKey(sub) && !used.contains(sub) && !(j == 0 && k == vals[i].length() - 1)) {
						used.add(vals[i].substring(j, k+1));
						ans += occ.get(vals[i].substring(j, k+1));
						// System.out.println(sub + " " +  vals[i]);
						// occ.put(vals[i].substring(j, k+1), occ.get(vals[i].substring(j, k+1)) + 1);
					}
					
				}
			}
		}
		PrintWriter pw = new PrintWriter(System.out);
		pw.println(ans);
		pw.close();
	}

}

• Subtask 1: 100 / 100