Как найти все подмассивы в массиве

An array is a linear data structure in which elements are stored in contiguous memory locations.

As per problem statement, we have to find all the subarrays of a given array. Subarrays are part or a section of an array. When we talk about all subarrays of an array, we talk about the total number of combinations that can be made using all the elements of the array without repeating.

Let’s explore the article to see how it can be done by using Java programming language.

To Show you Some Instances

Instance-1

Suppose we have the below array

[10, 2, 3, -5, 99, 12, 0, -1]

The subarrays of this array would be

10
10 2
10 2 3
10 2 3 -5
10 2 3 -5 99
10 2 3 -5 99 12
10 2 3 -5 99 12 0
10 2 3 -5 99 12 0 -1
2
2 3
2 3 -5
2 3 -5 99
2 3 -5 99 12
2 3 -5 99 12 0
2 3 -5 99 12 0 -1
3
3 -5
3 -5 99
3 -5 99 12
3 -5 99 12 0
3 -5 99 12 0 -1
-5
-5 99
-5 99 12
-5 99 12 0
-5 99 12 0 -1
99
99 12
99 12 0
99 12 0 -1
12
12 0
12 0 -1
0
0 -1
-1

Instance-2

Suppose we have the below array

[55,10,29,74]

The subarrays of this array would be

55
55 10
55 10 29
55 10 29 74
10
10 29
10 29 74
29
29 74
74

Algorithm

Algorithm-1

• Step 1 − After storing the array, run a for loop from 0 to n. This will mark our starting point of the main array.

• Step 2 − Run another for loop that runs from the first iterator to the ending point of the main array.

• Step 3 − Now run another loop that traverses the elements between both two iterators.

• Step 4 − Print the elements in a sequential order.

Algorithm-2

• Step 1 − After storing the array, check if we have reached the end, then go out of the function.

• Step 2 − If the start index is greater than the end index, then call the function itself from 0 to end+1.

• Step 3 − Else print the array elements between the indices inside a for loop, and call the function again from start+1 to end.

• Step 4 − Exit.

Syntax

To get the length of an array (number of elements in that array), there is an inbuilt property of array i.e length

Below refers to the syntax of it −

array.length

where, ‘array’ refers to the array reference.

You can use Arrays.sort() method to sort the array in ascending order.

Arrays.sort(array_name);

Multiple Approaches

We have provided the solution in different approaches.

• By Using for Loops

• By Using Recursion

Let’s see the program along with its output one by one.

Approach-1: By Using for Loops

In this approach, we will use three for loops to find the subarrays of an array. The first loop to mark the start and the second to mark the end of the subarray, while the third prints the subarray.

Example

import java.io.*;
public class Main {
   public static void main(String[] args) {
      
      // The array elements
      int arr[] = { 10, 2, 3, 99, 12, 0 };
      System.out.println("The subarrays are-");
      
      // For loop for start index
      for (int i = 0; i < arr.length; i++)
      
      // For loop for end index
      for (int j = i; j < arr.length; j++) {
      
         // For loop to print subarray elements
         for (int k = i; k <=j; k++)
            System.out.print(arr[k] + " ");
            System.out.println("");
      }
   }
}

Output

The subarrays are-
10 
10 2 
10 2 3 
10 2 3 99 
10 2 3 99 12 
10 2 3 99 12 0 
2 
2 3 
2 3 99 
2 3 99 12 
2 3 99 12 0 
3 3 99 3 99 12 3 99 12 0 
99 
99 12 
99 12 0 
12 12 0 
0 

Approach-2: By Using Recursion

In this approach, we find all the subarrays but using recursion.

Example

import java.io.*;
public class Main {
   //main method
   public static void main(String[] args) {
      // The array elements
      int arr[] = { 10, 2, 3};
      System.out.println("The subarrays are-");
         
      // Calling the recursive function
      printSubArrays(arr, 0, 0);
   }
   
   // Recursive FUnction to Find all the subarrays
   static void printSubArrays(int[] arr, int head, int tail) {
   
      // Exits the function if we have reached the end
      if (tail == arr.length)
         return;
      
      // Increases the first index and calls itself
      else if (head > tail)
         printSubArrays(arr, 0, tail + 1);
      
      // Print the subarray and then increases the first element index
      else {
         for (int i = head; i < tail; i++)
            System.out.print(arr[i] + " ");
         System.out.println(arr[tail]);
         printSubArrays(arr, head + 1, tail);
      }
      return;
   }
}

Output

The subarrays are-
10
10 2
2
10 2 3
2 3
3

In this article, we explored how to find all the subarrays of a given array by using Java programming language.

Это базовый алгоритм, но он в большинстве ситуациях будет работать за O(N) операций. Понять это можно через просмотр условия внутреннего цикла, до второй итерации будет очень редко доходить, а тем более до третий и далее.

Худший случай достигается при ситуации base = [1,1,1,1,1,1,1,1,1] find = [1,1,1,1]. Но вы думаете что есть алгоритм, который в такой ситуации сработает быстрее? Ну может быть и есть, но подобные ‘долгие’ ситуации очень редки, если брать все возможности ситуаций. И возможно даже если асимптотически такой алгоритм для таких ситуаций будет работать быстрее, то скорее всего из-за его сложности он будет работать медленнее на базовых ситуациях, что в результате сделает его медленнее в среднем. Вообщем я бы не стал дальше пытаться его оптимизировать.

var base = [1, 1, 1, 2, 3, 4, 5, 6, 1, 1, 2, 3, 1, 1, 2, 3];
var find = [1, 1, 2, 3];
var rez = [];
var yes;

var max = base.length - find.length;

for (var i = 0; i <= max; i++) {
  yes = true;

  for (var j = 0; j < find.length; j++) {
    if (base[i + j] != find[j]) {
      yes = false;
      break;
    }
  }

  if (yes) {
    rez.push(i);
  }
}

console.log(rez);

Обновлено

Для максимально быстрого поиска необходимо использовать конечные автоматы.

Смотрим алгоритм Ахо — Корасик.

5 ответов

Лучший ответ

#include <stdio.h>

int main(){
    int A[] = {1,2,3,4,5};
    int len=sizeof(A)/sizeof(int);
    for( int i=0; i<len; i++ ){
        for( int j=i; j<len; j++ ){   // Now A[i..j] is the subarray
            for( int k=i; k<=j; k++ )
                printf("%d ", A[k]);
            printf("n");
        }
    }
    return 0;
}

Array x;
collection SubArrays= {0}
SubArrays.AddSubArrays(x,0);

collection AddSubArrays(array, init,next){
 if(next>array.limit){
  return {0};
 }
 collection c.Add(array[init]
 while return not {0}
 i=init+1;
 while return not {0}
 c.AddSubArrays(array,init+1,i)
 i= i+1
 endwhile
 return c
}

       #include<bits/stdc++.h>
       using namespace std;


       void generateSubstring(string str)
       {
            if(str.size()==0)
            {
                return;
            }
            else
            {
                for(int i=0; i<str.size(); i++)
                {
                    for(int j=1; j<=str.size()-i; j++)
                    {
                        cout<<str.substr(i, i+j)<<endl;
                    }
                }
            }
        }


        int main()
        {
            ios::sync_with_stdio(false);
            string str;
            getline(cin, str);
            generateSubstring(str);
            return 0;
        }

def subarray(a, n) :
      for i in range(0,n):
             for j in range(i, n) :
                   for k in range(i, j+1) :
                          print(a(k), end=" ")
                   print("n", end=" ")
a=[1, 2,3,4,5]
n=len(a)
print( all non - empty subarrays are:-)
subarray(a, n) 

function subarray(arr){
  let sub = []
  for(let i=0;i<=arr.length-1;i++){
    for(let j=arr.length-1;j>=i;j--){
      sub.push(arr.slice(i,j+1))
    }
  }
  return sub
}