fork download
copy 
  1. import java.util.*;
  2.  
  3. class Ideone
  4. {
  5. 	public static void main (String[] args) throws java.lang.Exception
  6. 	{
  7. 		StringSearcher ss = new StringSearcher(new String[]{"abc", "def", "gh", "ghi", "ab"}, false);
  8. 		System.out.println(ss.matches("abd"));
  9. 		System.out.println(ss.matches("fghij"));
  10. 		System.out.println(ss.matches("fgij"));
  11. 	}
  12.  
  13. 	public static class NeedleTree{
  14. 		private int codePoint;
  15. 		private boolean selfSet = false;
  16. 		private Map<Integer, NeedleTree> children = new HashMap<>();
  17.  
  18. 		public NeedleTree(int codePoint){
  19. 			this.codePoint = codePoint;
  20. 		}
  21.  
  22. 		public NeedleTree childOrNull(int codePoint){
  23. 			return children.get(codePoint);
  24. 		}
  25.  
  26. 		public NeedleTree child(int codePoint){
  27. 			NeedleTree child = children.get(codePoint);
  28. 			if(child == null){
  29. 				children.put(codePoint, child = new NeedleTree(codePoint));
  30. 			}
  31. 			return child;
  32. 		}
  33.  
  34. 		public boolean isSelfSet(){
  35. 			return selfSet;
  36. 		}
  37.  
  38. 		public void markSelfSet(){
  39. 			selfSet = true;
  40. 		}
  41. 	}
  42.  
  43. 	public static class StringSearcher{
  44. 		private NeedleTree needles = new NeedleTree(-1);
  45. 		private boolean caseSensitive;
  46. 		private List<Integer> lengths = new ArrayList<>();
  47. 		private int maxLength;
  48.  
  49. 		public StringSearcher(String[] inputs, boolean caseSensitive){
  50. 			this(Arrays.asList(inputs), caseSensitive);
  51. 		}
  52. 		public StringSearcher(List<String> inputs, boolean caseSensitive){
  53. 			this.caseSensitive = caseSensitive;
  54. 			for(String input : inputs){
  55. 				if(!lengths.contains(input.length())){
  56. 					lengths.add(input.length());
  57. 				}
  58. 				NeedleTree tree = needles;
  59. 				for(int i = 0; i < input.length(); i++){
  60. 					tree = tree.child(caseSensitive ? input.codePointAt(i) : Character.toLowerCase(input.codePointAt(i)));
  61. 				}
  62. 				tree.markSelfSet();
  63. 			}
  64. 			maxLength = Collections.max(lengths);
  65. 		}
  66.  
  67. 		public boolean matches(String haystack){
  68. 			if(!caseSensitive){
  69. 				haystack = haystack.toLowerCase();
  70. 			}
  71. 			for(int i = 0; i < haystack.length(); i++){
  72. 				String substring = haystack.substring(i, Math.min(i + maxLength, haystack.length())); // maybe we can even skip this and use from haystack directly?
  73. 				NeedleTree tree = needles;
  74. 				for(int j = 0; j < substring.length(); j++){
  75. 					tree = tree.childOrNull(substring.codePointAt(j));
  76. 					if(tree == null){
  77. 						break;
  78. 					}
  79. 					if(tree.isSelfSet()){
  80. 						return true;
  81. 					}
  82. 				}
  83. 			}
  84. 			return false;
  85. 		}
  86. 	}
  87. }
Success #stdin #stdout 0.1s 321600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
false
https://ideone.com/e9xEiB
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!