How can we find a sub array in a 1-D array? Is there any other method other than brute force method?
It is not for maximum sum so we can't use kadane's algorithm.
menonnik
0
Newbie Poster
Recommended Answers
Jump to Postwhat kind of an array are you talking about? use strchr() or strstr() with character arrays.
Jump to PostMost of the fast string searching algorithms can be applied to non-string arrays as well.
All 8 Replies
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
what kind of an array are you talking about? use strchr() or strstr() with character arrays.
menonnik
0
Newbie Poster
an array with numbers.
Narue
5,707
Bad Cop
Team Colleague
Most of the fast string searching algorithms can be applied to non-string arrays as well.
menonnik
0
Newbie Poster
But I'm not not searching. I want to perform some operation on the subsets.(which is not sum) So how will string search algorithms help me?
I looked up one algortihm Boyer-Moore algorithm but it's not of any help.
TrustyTony
888
pyMod
Team Colleague
Featured Poster
That is really dependent of the nature of function applied and if there is overlap with previous answers and recursive function, you can sometimes reverse it to build dynamic programming solution or if it is difficult use memoized recursive function. I have recently done some subrange sums, but not in C.
menonnik
0
Newbie Poster
for eg. if we need to find a sub array such that the (sum of the sub array) mod b is atleast equal to k, then what are the sort of functions that we can use?
TrustyTony
888
pyMod
Team Colleague
Featured Poster
Are all values positive, if not bow you define modulo for negative values?
How many values there are in array?
How big is b, how is range of values, are they random or for example typically small?
menonnik
0
Newbie Poster
the values are positive. there can be around 50 values in the array. b can be anything between 1 and 1000000.
But i'm looking for a general algorithm that can be used for all functions not for this one specifically.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.