import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
String input
= "this is a markov chain, this is not a markov chain"; final int N = 2;
HashMap
<String, HashMap
<String, Integer
>> prefixes
= generatePrefixes
(input, N
);
}
public static HashMap
<String, HashMap
<String, Integer
>> generatePrefixes
(String input,
int n
) {
String[] words
= input.
split(" "); for (int i = 0; i < words.length-2; i++)
{
HashMap
<String, Integer
> suffixes
= new HashMap
<String, Integer
>(); suffixes.put(words[i+2], 1);
if (prefixes.get(words[i] + words[i+1]).get(words[i+2]) == null)
{
prefixes.put(words[i] + words[i+1], suffixes);
}
else
{
suffixes.put(words[i+2], prefixes.get(words[i] + words[i+1]).get(words[i+2])+1);
prefixes.put(words[i] + words[i+1], suffixes);
}
}
return prefixes;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVN0cmluZyBpbnB1dCA9ICJ0aGlzIGlzIGEgbWFya292IGNoYWluLCB0aGlzIGlzIG5vdCBhIG1hcmtvdiBjaGFpbiI7CgkJZmluYWwgaW50IE4gPSAyOwoJCUhhc2hNYXA8U3RyaW5nLCBIYXNoTWFwPFN0cmluZywgSW50ZWdlcj4+IHByZWZpeGVzID0gZ2VuZXJhdGVQcmVmaXhlcyhpbnB1dCwgTik7CgkJCgkJCgl9CgkKCXB1YmxpYyBzdGF0aWMgSGFzaE1hcDxTdHJpbmcsIEhhc2hNYXA8U3RyaW5nLCBJbnRlZ2VyPj4gZ2VuZXJhdGVQcmVmaXhlcyhTdHJpbmcgaW5wdXQsIGludCBuKQoJewoJCUhhc2hNYXA8U3RyaW5nLCBIYXNoTWFwPFN0cmluZywgSW50ZWdlcj4+IHByZWZpeGVzID0gbmV3IEhhc2hNYXA8U3RyaW5nLCBIYXNoTWFwPFN0cmluZywgSW50ZWdlcj4+KCk7CgkJU3RyaW5nW10gd29yZHMgPSBpbnB1dC5zcGxpdCgiICIpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgd29yZHMubGVuZ3RoLTI7IGkrKykKCQl7CgkJCUhhc2hNYXA8U3RyaW5nLCBJbnRlZ2VyPiBzdWZmaXhlcyA9IG5ldyBIYXNoTWFwPFN0cmluZywgSW50ZWdlcj4oKTsKCQkJc3VmZml4ZXMucHV0KHdvcmRzW2krMl0sIDEpOwoJCQkKCQkJaWYgKHByZWZpeGVzLmdldCh3b3Jkc1tpXSArIHdvcmRzW2krMV0pLmdldCh3b3Jkc1tpKzJdKSA9PSBudWxsKQoJCQl7CgkJCQlwcmVmaXhlcy5wdXQod29yZHNbaV0gKyB3b3Jkc1tpKzFdLCBzdWZmaXhlcyk7CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlzdWZmaXhlcy5wdXQod29yZHNbaSsyXSwgcHJlZml4ZXMuZ2V0KHdvcmRzW2ldICsgd29yZHNbaSsxXSkuZ2V0KHdvcmRzW2krMl0pKzEpOwoJCQkJcHJlZml4ZXMucHV0KHdvcmRzW2ldICsgd29yZHNbaSsxXSwgc3VmZml4ZXMpOwoJCQl9CgkJfQoJCXJldHVybiBwcmVmaXhlczsKCX0KCQoJCn0=