string finding

[newlang]

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

[proghelper]

Have you looked into strcmp and strncmp?

IF you want to write your own, u could use a for loop and keep on looking
for the first char and when that found, look for the second car.

John Dirk
Programming Consulant
http://www.programminghelp4u.com - Programming (Assignment/Project) Help

[pete]

ne*****@gmail.com wrote:

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

#include <string.h>

char *str_str(const char *s1, const char *s2)
{
const int c = *s2++;

if (c != '\0') {
const size_t n = strlen(s2);

s1 = strchr(s1, c);
while (s1 != NULL && strncmp(s1 + 1, s2, n) != 0) {
s1 = strchr(s1 + 1, c);
}
}
return (char *)s1;
}

--
pete

[Flash Gordon]

proghelper wrote:

Have you looked into strcmp and strncmp?

IF you want to write your own, u could use a for loop and keep on looking

Please don't use abbreviations link "u". It makes it harder to read your
posts and makes you look stupid.

Please always quote enough of the original post to provide context since
the way Usenet works means that people might not, and indeed may
never, see the message you are replying to.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Yohji]

ne*****@gmail.com wrote:

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

Try to rewrite strstr() function by yourself,it's very easy,isn't
it?And you can rewrite most of the functions in string.h,it's fun to do
that.

[vinodit205]

Use strstr routine defined in string.h

[Gregory Pietsch]

ne*****@gmail.com wrote:

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

/* The following is a public-domain implementation of the strstr()
function and the functions it calls in the <string.h> header. */

#include <string.h>

/* memcmp */
int (memcmp)(const void *s1, const void *s2, size_t n)
{
unsigned char *us1 = (unsigned char *) s1;
unsigned char *us2 = (unsigned char *) s2;
while (n-- != 0) {
if (*us1 != *us2)
return (*us1 < *us2) ? -1 : +1;
us1++;
us2++;
}
return 0;
}

/* strchr */
char *(strchr)(const char *s, int c)
{
/* Scan s for the character. When this loop is finished,
s will either point to the end of the string or the
character we were looking for. */
while (*s != '\0' && *s != c)
s++;
return ( (*s == c) ? (char *) s : NULL );
}

/* strlen */
size_t (strlen)(const char *s)
{
char *p = strchr(s, '\0');
return (p - s);
}

/* strstr */
char *(strstr)(const char *s1, const char *s2)
{
size_t s2len;
/* Check for the null s2 case. */
if (*s2 == '\0')
return (char *) s1;
s2len = strlen(s2);
for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
if (memcmp(s1, s2, s2len) == 0)
return (char *) s1;
return NULL;
}

/* Hopefully this helps ... Gregory Pietsch */

[jburgy]

ne*****@gmail.com wrote:

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

This is not strictly topical but I'll bite regardless. It depends on
how cute you want to get. You can simply use strstr, or roll your own
implementation if you think you're smarter than whoever implemented
your library (search comp.lang.c for strstr and timing for a thread
with sample code). If you want to be even fancier, you can use
Boyer-Moore or Knuth-Morris-Pratt algorithms. Thierry Lecroq in Rouen
has a very good online text (Exact String Matching Algorithms) with
sample code in C and animations in Java. Knock yourself out

Jan

[SM Ryan]

ne*****@gmail.com wrote:
# Hello everyone,
# I am eager to know about string functions, (user defined) . tell me
# the technique of find a string in another string.

Unless you have a reason not to use, strstr does this for you.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
If you plan to shoplift, let us know.
Thanks

[Default User]

ne*****@gmail.com wrote:

Hello everyone,
I am eager to know about string functions, (user defined) . tell me
the technique of find a string in another string.

Why do you want user-defined ones? What's wrong the standard ones?


Brian

[pete]

Gregory Pietsch wrote:

/* strlen */
size_t (strlen)(const char *s)
{
char *p = strchr(s, '\0');
return (p - s);
}

The ptrdiff_t type isn't guaranteed to be able
to represent the length of an arbitrary string.
(p - s) could be undefined.

[pete]

Gregory Pietsch wrote:

/* strstr */
char *(strstr)(const char *s1, const char *s2)
{
size_t s2len;
/* Check for the null s2 case. */
if (*s2 == '\0')
return (char *) s1;
s2len = strlen(s2);
for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
if (memcmp(s1, s2, s2len) == 0)
return (char *) s1;
return NULL;
}

The memcmp call is wrong. Should be strncmp instead.

Say for example, s2len is equal to sizeof(int),
then memcmp may attempt to access and compare sizeof(int) bytes
simultaneously, even though length of s1 may be zero, in which
case memcmp would be attempting to access unreserved memory.

[pete]

Gregory Pietsch wrote:

#include <string.h>

/* memcmp */
int (memcmp)(const void *s1, const void *s2, size_t n)
{
unsigned char *us1 = (unsigned char *) s1;
unsigned char *us2 = (unsigned char *) s2;

I think it's more better to match the qualifiers than to use casts.

int (memcmp)(const void *s1, const void *s2, size_t n)
{
const unsigned char *us1 = s1;
const unsigned char *us2 = s2;

--
pete

[pete]

Gregory Pietsch wrote:

/* strchr */
char *(strchr)(const char *s, int c)
{
/* Scan s for the character. When this loop is finished,
s will either point to the end of the string or the
character we were looking for. */
while (*s != '\0' && *s != c)
The value of c is supposed to be converted to type char.

while (*s != '\0' && *s != (char)c)
s++;
return ( (*s == c) ? (char *) s : NULL );
}

return ( (*s == (char)c) ? (char *) s : NULL );

--
pete

[Old Wolf]

pete wrote:

Gregory Pietsch wrote:

/* strlen */
size_t (strlen)(const char *s)
{
char *p = strchr(s, '\0');
return (p - s);
}

The ptrdiff_t type isn't guaranteed to be able
to represent the length of an arbitrary string.
(p - s) could be undefined.

Doesn't that make ptrdiff_t fairly useless in practice, if
it can't safely represent the difference between two pointers?

Is it possible to portably get a size_t that holds the difference
between s and p, short of something like:

size_t n = 0; while (s++ != p) ++n;

[pete]

Old Wolf wrote:

pete wrote:

Gregory Pietsch wrote:

/* strlen */
size_t (strlen)(const char *s)
{
char *p = strchr(s, '\0');
return (p - s);
}
The ptrdiff_t type isn't guaranteed to be able
to represent the length of an arbitrary string.
(p - s) could be undefined.

Doesn't that make ptrdiff_t fairly useless in practice, if
it can't safely represent the difference between two pointers?

ptrdiff_t is unsuitable for a lot of things.

Sometimes you know that the limits of what an algorithm
can generate, will fall within what ptrdiff_t can represent.

#define UPPER "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER "abcdefghijklmnopqrstuvwxyz"

int to_upper(int c)
{
const char *upper;
const char *const lower = LOWER;

upper = CHAR_MAX >= c && c > '\0' ? strchr(lower, c) : NULL;
return upper != NULL ? UPPER[upper - lower] : c;
}
Is it possible to portably get a size_t that holds the difference
between s and p, short of something like:

size_t n = 0; while (s++ != p) ++n;

size_t str_len(const char *s)
{
size_t n;

for (n = 0; s[n] != '\0'; ++n) {
;
}
return n;
}

--
pete

[Gregory Pietsch]

pete wrote:

Gregory Pietsch wrote:

/* strlen */
size_t (strlen)(const char *s)
{
char *p = strchr(s, '\0');
return (p - s);
}

The ptrdiff_t type isn't guaranteed to be able
to represent the length of an arbitrary string.
(p - s) could be undefined.

Well, it was easier than typing

size_t (strlen)(const char *s)
{
size_t r = 0;

while (s[r] != '\0')
r++;
return r;
}

which also works.

Gregory

[Gregory Pietsch]

pete wrote:

Gregory Pietsch wrote:

/* strstr */
char *(strstr)(const char *s1, const char *s2)
{
size_t s2len;
/* Check for the null s2 case. */
if (*s2 == '\0')
return (char *) s1;
s2len = strlen(s2);
for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
if (memcmp(s1, s2, s2len) == 0)
return (char *) s1;
return NULL;
}

The memcmp call is wrong. Should be strncmp instead.

Say for example, s2len is equal to sizeof(int),
then memcmp may attempt to access and compare sizeof(int) bytes
simultaneously, even though length of s1 may be zero, in which
case memcmp would be attempting to access unreserved memory.

If the length of s1 is zero, the code never reaches the memcmp() call.
The memcmp() call will return nonzero anyway when it compares the '\0'
against a positive value. Even if the unreserved memory is accessed, it
is unmodified.

Gregory

[pete]

Gregory Pietsch wrote:

pete wrote:

Gregory Pietsch wrote:

/* strstr */
char *(strstr)(const char *s1, const char *s2)
{
size_t s2len;
/* Check for the null s2 case. */
if (*s2 == '\0')
return (char *) s1;
s2len = strlen(s2);
for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
if (memcmp(s1, s2, s2len) == 0)
return (char *) s1;
return NULL;
}
The memcmp call is wrong. Should be strncmp instead.

Say for example, s2len is equal to sizeof(int),
then memcmp may attempt to access and compare sizeof(int) bytes
simultaneously, even though length of s1 may be zero, in which
case memcmp would be attempting to access unreserved memory.

If the length of s1 is zero, the code never reaches the memcmp() call.

OK. Instead, consider if the length of s1 was
any positive value less than (s2len - 1)
The memcmp() call will return nonzero anyway when it compares the '\0'
against a positive value.
Even if the unreserved memory is accessed, it is unmodified.

Unmodified or not, doesn't matter.
It's still undefined behavior to attempt the access
of memory beyond an array boundry.

--
pete

[Gregory Pietsch]

pete wrote:

Gregory Pietsch wrote:

pete wrote:

Gregory Pietsch wrote:

> /* strstr */
> char *(strstr)(const char *s1, const char *s2)
> {
> size_t s2len;
> /* Check for the null s2 case. */
> if (*s2 == '\0')
> return (char *) s1;
> s2len = strlen(s2);
> for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
> if (memcmp(s1, s2, s2len) == 0)
> return (char *) s1;
> return NULL;
> }

The memcmp call is wrong. Should be strncmp instead.

Say for example, s2len is equal to sizeof(int),
then memcmp may attempt to access and compare sizeof(int) bytes
simultaneously, even though length of s1 may be zero, in which
case memcmp would be attempting to access unreserved memory.
If the length of s1 is zero, the code never reaches the memcmp() call.

OK. Instead, consider if the length of s1 was
any positive value less than (s2len - 1)

Then it reaches the memcmp() call. The way I wrote memcmp() above, it
returns nonzero when it compares '\0' against a positive value, without
reaching unreserved memory.

The memcmp() call will return nonzero anyway when it compares the '\0'
against a positive value.
Even if the unreserved memory is accessed, it is unmodified.

Unmodified or not, doesn't matter.
It's still undefined behavior to attempt the access
of memory beyond an array boundry.

And the way I wrote memcmp() above, it doesn't.
--
pete

Gregory Pietsch

[pete]

Gregory Pietsch wrote:

pete wrote:

Gregory Pietsch wrote:

pete wrote:
> Gregory Pietsch wrote:
>
> > /* strstr */
> > char *(strstr)(const char *s1, const char *s2)
> > {
> > size_t s2len;
> > /* Check for the null s2 case. */
> > if (*s2 == '\0')
> > return (char *) s1;
> > s2len = strlen(s2);
> > for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
> > if (memcmp(s1, s2, s2len) == 0)
> > return (char *) s1;
> > return NULL;
> > }
>
> The memcmp call is wrong. Should be strncmp instead.

And the way I wrote memcmp() above, it doesn't.

I have a toy string library, as I suspect you do,
but I only use function calls in my function definitions
in cases where the real library functions would also do the trick.
My main goals are
1 trying to get the definitions correct
2 showing any relationships that may exist between
what various standard library functions do.

If you rewrite the above strstr function definition
with strncmp instead of memcmp,
then you are showing a relationship that really exists between
what the standard library functions strstr and strncmp do.

I don't think there's any real value
in showing that what strstr does,
can be described by your specific implementation of memcmp.

--
pete

[Gregory Pietsch]

pete wrote:

Gregory Pietsch wrote:

pete wrote:

Gregory Pietsch wrote:
>
> pete wrote:
> > Gregory Pietsch wrote:
> >
> > > /* strstr */
> > > char *(strstr)(const char *s1, const char *s2)
> > > {
> > > size_t s2len;
> > > /* Check for the null s2 case. */
> > > if (*s2 == '\0')
> > > return (char *) s1;
> > > s2len = strlen(s2);
> > > for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
> > > if (memcmp(s1, s2, s2len) == 0)
> > > return (char *) s1;
> > > return NULL;
> > > }
> >
> > The memcmp call is wrong. Should be strncmp instead.

And the way I wrote memcmp() above, it doesn't.

I have a toy string library, as I suspect you do,
but I only use function calls in my function definitions
in cases where the real library functions would also do the trick.
My main goals are
1 trying to get the definitions correct
2 showing any relationships that may exist between
what various standard library functions do.

The string.h header is a hodgepodge. It represents not a concerted
design effort but rather the accretion of contributions made by various
authors over a span of years.
If you rewrite the above strstr function definition
with strncmp instead of memcmp,
then you are showing a relationship that really exists between
what the standard library functions strstr and strncmp do.

I could write it correctly with neither:

#include <string.h>
char *(strstr)(const char *s1, const char *s2)
{
const char *sc1, *sc2;

if (*s2 == '\0')
return (char *) s1; /* takes care of null s2 case */
while ((s1 = strchr(s1, *s2)) != NULL) {
sc1 = s1;
sc2 = s2;
while ( 1 ) {
/* match rest of prefix */
if (*++sc2 == '\0')
return (char *) s1;
else if (*++sc1 != *sc2)
break;
}
++s1;
}
return NULL;
}
I don't think there's any real value
in showing that what strstr does,
can be described by your specific implementation of memcmp.

I included it for completeness.
--
pete

Gregory Pietsch