1

I have two char arrays (e.g. arr[]1 {'w','o','r','d'} and arr[]2 {'o','r'}) and need to check for pattern occurrence of arr[]2 in arr[]1 (All values of arr2 must be present in arr1 in the same sequential order).

I already solved this by converting to strings and using regex. However, I was wondering if this could be solved without building strings consisting of the chars in each array.

Is it possible to check if an entire array is part of another one in JAVA (while keeping continuity/index sequence in account) or do I have to iterate through each value [n], [n+1],... [arr2.length] of arr2 and see if it is present in arr1[indexofFoundChar],[index+1]... and so on. Any help is greatly appreciated.

DoPh
  • 11
  • 2
  • Possible duplicate of [Finding if an array contains all elements in another array](https://stackoverflow.com/questions/16524709/finding-if-an-array-contains-all-elements-in-another-array) – Mark Nov 19 '18 at 09:11
  • Still using `String`, but without regex: `String.valueOf(arr1).contains(String.valueOf(arr2))`. – Jai Nov 19 '18 at 09:16
  • why not just use String and its `contains` methods, no need for regex... if you really need to do it yourself hava a look at the implementation of `contains`, or more precisely, `indexOf()` – user85421 Nov 19 '18 at 09:16
  • what about `arr[1]1 {'w', 'o', 'x', 'r'}` should it return `true` for above `arr[]2` ? – user85421 Nov 19 '18 at 09:28
  • {'w', 'o', 'x', 'r'} should return false, {'w', 'o', 'r', 'x'} for example should return true. – DoPh Nov 19 '18 at 09:33
  • How large are your arrays? – MBo Nov 19 '18 at 09:36
  • rather small, they consist of about 5-15 characters. – DoPh Nov 19 '18 at 09:43

1 Answers1

1

For so small arrays direct comparison (brute-force approach) should be enough. 

for (int i = 0; i < lenA - lenB; i++)  {
   int j = 0;
   while (j < lenB) && (B[j] = A[i+j])
      j++; 
   if (j==lenB)
       return true;
}
return false;

It works fast but becomes quadratic when repeating/partially matched patterns occur (like "abcabcd" when you look for "abcd")

For larger arrays choose any simple string searching algorithm like Boyer-Moore, Knutt-Morris-Pratt, Rabin-Karp ones - but apply them to array items, not strings.

MBo
  • 77,366
  • 5
  • 53
  • 86