Searching for a sub 'string' in another 'string'

Question

How would I write an efficient algorithm to search for a subset array of integers in another array in C? For example:

unsigned a[] = {42, 72, 61, 1023, 84, 42, 42, 193, 302, 72};
unsigned long al = 10;
unsigned b[] = {61, 1023, 84};
unsigned long bl = 3;

I've tried a brute-force approach, by looping through a and then looping through b if a[n] is b[0], but then backtracking if the match fails halfway. It seems like the best I can think of, but I'm sure there must be a faster way.

Rather than hardcoding the size, you can use sizeof(a) / sizeof(a[0]). — James McNellis
– James McNellis, Commented Sep 25, 2010 at 0:32
Thanks for the tip, though this is an example and in my program I have a struct that manages the dynamic memory plus the pointer's length. — Delan Azabani
– Delan Azabani, Commented Sep 25, 2010 at 0:33
I always thought C doesn't know the sizeof an array. It definitely can't tell you the length of an array. What's the difference? — AlcubierreDrive
– AlcubierreDrive, Commented Sep 25, 2010 at 0:35
In you, C do know the size of an array. What you don't know is the size of memory pointed to by a pointer. You cannot pass arrays as arguments to functions, so C automatically converts array arguments to pointers to their first element. Such a function will not know the size of its argument even though that argument is logically an array because what the function has access to is only a pointer. — Tyler McHenry
– Tyler McHenry, Commented Sep 25, 2010 at 0:38
That's why I manage it in my struct's functions, changing a separate length value as the data is manipulated so that the length is known. However, I think that in the case of [] arrays with fixed data, you can find the size at runtime. — Delan Azabani
– Delan Azabani, Commented Sep 25, 2010 at 0:39

Tyler McHenry · Accepted Answer · 2010-09-25 00:31:08Z

6

There are several well-known, efficient string searching algorithms and they will all work for this purpose. There's really no difference between an array of integers and an array of integers which have each been assigned to character representations if a subsequence is what you're looking for.

If your problem is really a small as what you've posted, it's probably not worth using anything except brute force, but I'm assuming that's just a toy example of what you want to do.

answered Sep 25, 2010 at 0:31

Tyler McHenry

77.2k18 gold badges127 silver badges171 bronze badges

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

1 Comment

Delan Azabani Over a year ago

Thanks for that! Sorry about not finding what was so close to me.

Collectives™ on Stack Overflow

Searching for a sub 'string' in another 'string'

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related