Java matching patterns in array

Question

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.

Possible duplicate of Finding if an array contains all elements in another array — Mark
– Mark, Commented Nov 19, 2018 at 9:11
Still using String, but without regex: String.valueOf(arr1).contains(String.valueOf(arr2)). — Jai
– Jai, Commented Nov 19, 2018 at 9: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
– user85421, Commented Nov 19, 2018 at 9:16
what about arr[1]1 {'w', 'o', 'x', 'r'} should it return true for above arr[]2 ? — user85421
– user85421, Commented Nov 19, 2018 at 9:28
{'w', 'o', 'x', 'r'} should return false, {'w', 'o', 'r', 'x'} for example should return true. — DoPh
– DoPh, Commented Nov 19, 2018 at 9:33

MBo · Accepted Answer · 2018-11-19 10:00:17Z

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.

answered Nov 19, 2018 at 10:00

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java matching patterns in array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related