PAL5_3-12_NEoop

package pal;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_Alisa {

    static public Integer MAX_PROPOSAL = 100000;
    static public String alphabet; // chars in alphabet
    static public int countMembers; //count of comittee memebers
    static public int countMembersAccept; // count of comittee memebers for acceptance of proposal
    static public int proposalLength; //length of word
    static public Set<String> UniqueProposals;//vschny unikatni prefixy
    static public Set<String> AcceptedPrposals; //prijate unikatni prefixy
    static public Set<String> AcceptedHighPrefixes;//jenom ty kratsi unikatni prefixy
    static public HashMap<String, Integer> UniqueProposalsEval; //ohodnocene unikatni prefixy
    static public Iterator it1;
    static public Iterator it2;
    public static Object[] high;
    public static BigInteger alphabetSize;

    public static final int bufferSize = 10000000;

    public static void main(String[] args) throws IOException {
        args = new String[]{"pub01.in"};

        BufferedReader br = (args.length == 0)
                ? new BufferedReader(new InputStreamReader(System.in), bufferSize)
                : new BufferedReader(new InputStreamReader(new FileInputStream(args[0])), bufferSize);
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in), bufferSize);

        StringTokenizer configuration = new StringTokenizer(br.readLine());
        alphabet = configuration.nextToken();
        alphabetSize = BigInteger.valueOf(alphabet.length());
        countMembers = Integer.parseInt(configuration.nextToken());
        countMembersAccept = Integer.parseInt(configuration.nextToken());
        proposalLength = Integer.parseInt(configuration.nextToken());

        UniqueProposals = new HashSet<>();
        AcceptedPrposals = new HashSet<>();
        UniqueProposalsEval = new HashMap<>();

        HashSet comitteeProposals; //uchovavame pouze unikatni navrhy clena
        int countOfProp;
        String prefixProp;

        for (int i = 0; i < countMembers; i++) {
            comitteeProposals = new HashSet();
            countOfProp = Integer.parseInt(br.readLine());
            for (int j = 0; j < countOfProp; j++) {
                prefixProp = br.readLine();
                //kazdemu clenu pridame jeho unikatni navrhy - mozna nebude potreba
                evaluateProposal(prefixProp, comitteeProposals);
            }
            //ohodnoceni a kontrola prefixu
            //  evaluateForOneComittee(comitteeProposals);
        }
        AcceptedHighPrefixes = new HashSet<>(AcceptedPrposals);

        Set<String> acceptedProposalPrefixes = filterRedundantPrefixes(AcceptedHighPrefixes);

        BigInteger result = countPossibilitiesFromPrefixes(acceptedProposalPrefixes, alphabetSize, proposalLength);

        System.out.println(result.mod(BigInteger.valueOf(MAX_PROPOSAL)));
    }

    public static void evaluateProposal(String proposal, HashSet comitteePropsal) {
        Integer valueOfExistingPrefix;
        HashMap<String, Integer> uniqueCopy;
        //kontroluje duplicitu u jednoho hlasujiciho
        if (comitteePropsal.add(proposal)) {

            if (!AcceptedPrposals.contains(proposal)) {
                if (UniqueProposals.add(proposal)) {
                    UniqueProposalsEval.put(proposal, 1);
                    valueOfExistingPrefix = UniqueProposalsEval.get(proposal);
                } else {
                    valueOfExistingPrefix = UniqueProposalsEval.get(proposal) + 1;
                    UniqueProposalsEval.put(proposal, valueOfExistingPrefix);
                }
                // && next.length()<=K
                if (valueOfExistingPrefix >= countMembersAccept) {
                    AcceptedPrposals.add(proposal);
                    //skoro by se tu hodil return :D kdyz navrh prijat, nema smysl projizde uniqueeval, ale zase si neumazem potomky
                }
                uniqueCopy = new HashMap<>(UniqueProposalsEval);

                //kdyz stringy zacinaji stejnym prefixem, odstranime vsechny vetsi potomky
                for (Map.Entry<String, Integer> entrySet : uniqueCopy.entrySet()) {
                    String key = entrySet.getKey();
                    Integer value = entrySet.getValue();
                    //key zacina prefixem a nejsou shodne -> vetsi
                    if (key.startsWith(proposal) && !key.equals(proposal)) {
                        value = value + 1; //pricteme hlas k proposal
                        UniqueProposalsEval.remove(key, value); //odstranime vetsiho potomka
                        if (value >= countMembersAccept) { //pokud proposal prijat, break
                            AcceptedPrposals.add(proposal);
                            break;
                        }
                    }
                }
                uniqueCopy = new HashMap<>(UniqueProposalsEval);
            }
        }
    }

    /***************************************************************************
     * Vrátí prefixy bez těch které jsou odvoditelné z prefixů nižšího řádu
     * @param acceptedPrefixes
     * @return
     */
    private static Set<String> filterRedundantPrefixes(Set<String> acceptedPrefixes) {
        Set<String> result = new HashSet<>();
        for (String prefix : acceptedPrefixes) {
            boolean acceptPrefix = true;
            for (String prefixCheck : acceptedPrefixes) {
                if (prefixCheck.length() < prefix.length() && prefix.startsWith(prefixCheck)) {
                    acceptPrefix = false;
                    break;
                }
            }
            if (acceptPrefix) {
                result.add(prefix);
            }
        }
        return result;
    }

    /***************************************************************************
     * Vrátí součet možných řešení které lze vygenerovat z prefixů v předané množině
     * @param prefixes
     * @param alphabetSize
     * @param proposalLength
     * @return
     */
    private static BigInteger countPossibilitiesFromPrefixes(Set<String> prefixes, BigInteger alphabetSize, int proposalLength) {
        BigInteger result = BigInteger.ZERO;
        for (String prefix : prefixes) {
            result = result.add(
                    BigInteger.ONE.multiply(
                            alphabetSize.pow(proposalLength - prefix.length())
                    )
            );
        }
        return result;
    }
}