import java.util.*;
class Ideone
{
{
StringSearcher ss
= new StringSearcher
(new String[]{"abc",
"def",
"gh",
"ghi",
"ab"},
false); System.
out.
println(ss.
matches("abd")); System.
out.
println(ss.
matches("fghij")); System.
out.
println(ss.
matches("fgij")); }
public static class NeedleTree{
private int codePoint;
private boolean selfSet = false;
private Map
<Integer, NeedleTree
> children
= new HashMap
<>();
public NeedleTree(int codePoint){
this.codePoint = codePoint;
}
public NeedleTree childOrNull(int codePoint){
return children.get(codePoint);
}
public NeedleTree child(int codePoint){
NeedleTree child = children.get(codePoint);
if(child == null){
children.put(codePoint, child = new NeedleTree(codePoint));
}
return child;
}
public boolean isSelfSet(){
return selfSet;
}
public void markSelfSet(){
selfSet = true;
}
}
public static class StringSearcher{
private NeedleTree needles = new NeedleTree(-1);
private boolean caseSensitive;
private List<Integer> lengths = new ArrayList<>();
private int maxLength;
public StringSearcher
(String[] inputs,
boolean caseSensitive
){ this(Arrays.
asList(inputs
), caseSensitive
); }
public StringSearcher(List<String> inputs, boolean caseSensitive){
this.caseSensitive = caseSensitive;
if(!lengths.contains(input.length())){
lengths.add(input.length());
}
NeedleTree tree = needles;
for(int i = 0; i < input.length(); i++){
tree
= tree.
child(caseSensitive
? input.
codePointAt(i
) : Character.
toLowerCase(input.
codePointAt(i
))); }
tree.markSelfSet();
}
}
public boolean matches
(String haystack
){ if(!caseSensitive){
haystack = haystack.toLowerCase();
}
for(int i = 0; i < haystack.length(); i++){
String substring
= haystack.
substring(i,
Math.
min(i
+ maxLength, haystack.
length())); // maybe we can even skip this and use from haystack directly? NeedleTree tree = needles;
for(int j = 0; j < substring.length(); j++){
tree = tree.childOrNull(substring.codePointAt(j));
if(tree == null){
break;
}
if(tree.isSelfSet()){
return true;
}
}
}
return false;
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVN0cmluZ1NlYXJjaGVyIHNzID0gbmV3IFN0cmluZ1NlYXJjaGVyKG5ldyBTdHJpbmdbXXsiYWJjIiwgImRlZiIsICJnaCIsICJnaGkiLCAiYWIifSwgZmFsc2UpOwoJCVN5c3RlbS5vdXQucHJpbnRsbihzcy5tYXRjaGVzKCJhYmQiKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKHNzLm1hdGNoZXMoImZnaGlqIikpOwoJCVN5c3RlbS5vdXQucHJpbnRsbihzcy5tYXRjaGVzKCJmZ2lqIikpOwoJfQoKCXB1YmxpYyBzdGF0aWMgY2xhc3MgTmVlZGxlVHJlZXsKCQlwcml2YXRlIGludCBjb2RlUG9pbnQ7CgkJcHJpdmF0ZSBib29sZWFuIHNlbGZTZXQgPSBmYWxzZTsKCQlwcml2YXRlIE1hcDxJbnRlZ2VyLCBOZWVkbGVUcmVlPiBjaGlsZHJlbiA9IG5ldyBIYXNoTWFwPD4oKTsKCQkKCQlwdWJsaWMgTmVlZGxlVHJlZShpbnQgY29kZVBvaW50KXsKCQkJdGhpcy5jb2RlUG9pbnQgPSBjb2RlUG9pbnQ7CgkJfQoJCQoJCXB1YmxpYyBOZWVkbGVUcmVlIGNoaWxkT3JOdWxsKGludCBjb2RlUG9pbnQpewoJCQlyZXR1cm4gY2hpbGRyZW4uZ2V0KGNvZGVQb2ludCk7CgkJfQoJCQoJCXB1YmxpYyBOZWVkbGVUcmVlIGNoaWxkKGludCBjb2RlUG9pbnQpewoJCQlOZWVkbGVUcmVlIGNoaWxkID0gY2hpbGRyZW4uZ2V0KGNvZGVQb2ludCk7CgkJCWlmKGNoaWxkID09IG51bGwpewoJCQkJY2hpbGRyZW4ucHV0KGNvZGVQb2ludCwgY2hpbGQgPSBuZXcgTmVlZGxlVHJlZShjb2RlUG9pbnQpKTsKCQkJfQoJCQlyZXR1cm4gY2hpbGQ7CgkJfQoJCgkJcHVibGljIGJvb2xlYW4gaXNTZWxmU2V0KCl7CgkJCXJldHVybiBzZWxmU2V0OwoJCX0KCQoJCXB1YmxpYyB2b2lkIG1hcmtTZWxmU2V0KCl7CgkJCXNlbGZTZXQgPSB0cnVlOwoJCX0KCX0KCQoJcHVibGljIHN0YXRpYyBjbGFzcyBTdHJpbmdTZWFyY2hlcnsKCQlwcml2YXRlIE5lZWRsZVRyZWUgbmVlZGxlcyA9IG5ldyBOZWVkbGVUcmVlKC0xKTsKCQlwcml2YXRlIGJvb2xlYW4gY2FzZVNlbnNpdGl2ZTsKCQlwcml2YXRlIExpc3Q8SW50ZWdlcj4gbGVuZ3RocyA9IG5ldyBBcnJheUxpc3Q8PigpOwoJCXByaXZhdGUgaW50IG1heExlbmd0aDsKCQoJCXB1YmxpYyBTdHJpbmdTZWFyY2hlcihTdHJpbmdbXSBpbnB1dHMsIGJvb2xlYW4gY2FzZVNlbnNpdGl2ZSl7CgkJCXRoaXMoQXJyYXlzLmFzTGlzdChpbnB1dHMpLCBjYXNlU2Vuc2l0aXZlKTsKCQl9CgkJcHVibGljIFN0cmluZ1NlYXJjaGVyKExpc3Q8U3RyaW5nPiBpbnB1dHMsIGJvb2xlYW4gY2FzZVNlbnNpdGl2ZSl7CgkJCXRoaXMuY2FzZVNlbnNpdGl2ZSA9IGNhc2VTZW5zaXRpdmU7CgkJCWZvcihTdHJpbmcgaW5wdXQgOiBpbnB1dHMpewoJCQkJaWYoIWxlbmd0aHMuY29udGFpbnMoaW5wdXQubGVuZ3RoKCkpKXsKCQkJCQlsZW5ndGhzLmFkZChpbnB1dC5sZW5ndGgoKSk7CgkJCQl9CgkJCQlOZWVkbGVUcmVlIHRyZWUgPSBuZWVkbGVzOwoJCQkJZm9yKGludCBpID0gMDsgaSA8IGlucHV0Lmxlbmd0aCgpOyBpKyspewoJCQkJCXRyZWUgPSB0cmVlLmNoaWxkKGNhc2VTZW5zaXRpdmUgPyBpbnB1dC5jb2RlUG9pbnRBdChpKSA6IENoYXJhY3Rlci50b0xvd2VyQ2FzZShpbnB1dC5jb2RlUG9pbnRBdChpKSkpOwoJCQkJfQoJCQkJdHJlZS5tYXJrU2VsZlNldCgpOwoJCQl9CgkJCW1heExlbmd0aCA9IENvbGxlY3Rpb25zLm1heChsZW5ndGhzKTsKCQl9CgkKCQlwdWJsaWMgYm9vbGVhbiBtYXRjaGVzKFN0cmluZyBoYXlzdGFjayl7CgkJCWlmKCFjYXNlU2Vuc2l0aXZlKXsKCQkJCWhheXN0YWNrID0gaGF5c3RhY2sudG9Mb3dlckNhc2UoKTsKCQkJfQoJCQlmb3IoaW50IGkgPSAwOyBpIDwgaGF5c3RhY2subGVuZ3RoKCk7IGkrKyl7CgkJCQlTdHJpbmcgc3Vic3RyaW5nID0gaGF5c3RhY2suc3Vic3RyaW5nKGksIE1hdGgubWluKGkgKyBtYXhMZW5ndGgsIGhheXN0YWNrLmxlbmd0aCgpKSk7IC8vIG1heWJlIHdlIGNhbiBldmVuIHNraXAgdGhpcyBhbmQgdXNlIGZyb20gaGF5c3RhY2sgZGlyZWN0bHk/CgkJCQlOZWVkbGVUcmVlIHRyZWUgPSBuZWVkbGVzOwoJCQkJZm9yKGludCBqID0gMDsgaiA8IHN1YnN0cmluZy5sZW5ndGgoKTsgaisrKXsKCQkJCQl0cmVlID0gdHJlZS5jaGlsZE9yTnVsbChzdWJzdHJpbmcuY29kZVBvaW50QXQoaikpOwoJCQkJCWlmKHRyZWUgPT0gbnVsbCl7CgkJCQkJCWJyZWFrOwoJCQkJCX0KCQkJCQlpZih0cmVlLmlzU2VsZlNldCgpKXsKCQkJCQkJcmV0dXJuIHRydWU7CgkJCQkJfQoJCQkJfQoJCQl9CgkJCXJldHVybiBmYWxzZTsKCQl9Cgl9Cn0=