KR2 Exercise 4-01 - clc-wiki

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.01 on page 71

Write the function strrindex(s,t) , which returns the position of the rightmost occurrence of t in s , or -1 if there is none.

Contents

1 Solution by Rick Dearman

2 Solution by Xggggg

3 Solution by Pilcrow

4 Solution by Adam89

5 Solution by menonsahab

6 Solution by Liangming

7 Solution by Luke Panayi

8 Solution by Miguel Degrossoli

9 Solution by anonymous

Solution by Rick Dearman

This solution below deals with "t" as a character, K&R requests for a modified version of the strindex done before in the chapter, which deals with "t" as a string. Xggggg 9:23, 5 August 2020 (UTC)

/* Test driver by Richard Heathfield
 * Solution (strrindex function) by Rick Dearman
 */

#include <stdio.h>

/* Write the function strrindex(s,t), which returns the position
** of the rightmost occurrence of t in s, or -1 if there is none.
*/

int strrindex( char s[], char t )
{
  int i;
  int count = -1;

  for(i=0; s[i] != '\0'; i++)
  {
    if(s[i] == t)
    {
      count = i;
    }
  }

  return count;
}


typedef struct TEST
{
  char *data;
  char testchar;
  int expected;
} TEST;

int main(void)
{
  TEST test[] =
  {
    {"Hello world", 'o', 7},
    {"This string is littered with iiiis", 'i', 32},
    {"No 'see' letters in here", 'c', -1}
  };

  size_t numtests = sizeof test / sizeof test[0];
  size_t i;

  char ch = 'o';
  int pos;

  for(i = 0; i < numtests; i++)
  {
    pos = strrindex(test[i].data, test[i].testchar);

    printf("Searching %s for last occurrence of %c.\n",
           test[i].data,
           test[i].testchar);

    printf("Expected result: %d\n", test[i].expected);
    printf("%sorrect (%d).\n", pos == test[i].expected ? "C" : "Inc", pos);
    if(pos != -1)
    {
      printf("Character found was %c\n", test[i].data[pos]);
    }
  }

  return 0;
}

Solution by Xggggg

#include <stdio.h>
#include <string.h>

int strindex(const char s[], const char t[]);

int main(void)
{
	printf("%d\n", strindex("I stopped dreaming a long long time ago", "long"));
	return 0;
}

int strindex(const char s[], const char t[])
{
	for (int i = strlen(s) - 1, j; i >= 0; i--)
	{
		for (j = 0; s[i + j] == t[j] && t[j]; j++);
		if (!t[j])
			return i;
	}
	return -1;
}

Solution by Pilcrow

/*****************************************************
Maybe my mind isn't complicated enough, but I thought
what was wanted was the rightmost position of one 
string in another. See K&R2 p69. -- Pilcrow
*****************************************************/

#include <stdio.h>
#include <string.h>

int strrindex(char[], char[]);

int main()
{
    char s[] = "cqabcdef";
    char t[] = "ef";
    char u[] = "cd";
    char v[] = "cqa";
    char z[] = "gh";
    int i;
    i = strrindex(s, t);
    if (i >=0)printf("'%s' matches '%s' at index %d\n",t,s,i);
    else printf("'%s' doesn't match '%s' at all\n",t,s);

    i = strrindex(s, u);
    if (i >=0)printf("'%s' matches '%s' at index %d\n",u,s,i);
    else printf("'%s' doesn't match '%s' at all\n",u,s);

    i = strrindex(s, v);
    if (i >=0)printf("'%s' matches '%s' at index %d\n",v,s,i);
    else printf("'%s' doesn't match '%s' at all\n",v,s);

    i = strrindex(s, z);
    if (i >=0)printf("'%s' matches '%s' at index %d\n",z,s,i);
    else printf("'%s' doesn't match '%s' at all\n",z,s);


    return 0;
}

int strrindex(char s[], char t[])
{
    int ls, lt, is, is2, it, match;
    ls = strlen( s);
    lt = strlen( t);
    match = -1;
    for(is = ls -1; is >= 0; is--) {
        for(it = 0, is2 = is; it < lt; it++, is2++) {
            if(t[it] != s[is2]){
                match = -1;
                break;
            }
            match = is;
        }
        if(it >= lt)return match;
    }
    return match;
}

Solution by Adam89

/*************************************************************
strrindex will return the rightmost starting position of t in s.
I thought this was neat as it's simply the original strindex 
function from K&R page 69 with the smallest of changes.  I
interpreted the exercise as asking for the index of s at which
the final occurence of t begins e.g. for "aaZ" in "aaZZaaaZZaaZa"
the answer would be 9.
*************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int strrindex(char s[], char t[]);

int main()
{
        int i;
	char parent[] = "A String with some letters in it.";
	char child[] = "in";
        i = strrindex(parent, child);
        printf("%d\n",i); // In this case, the program will print the number 27.
        return 0;
}

int strrindex(char s[], char t[])
{
	int i, j, k, m = -1;
        for (i = 0; s[i] != '\0'; i++)
	{
		for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++)
			;
		if (k > 0 && t[k] == '\0')
			m = i;
	}
        return m;
}

Solution by menonsahab

/* I'm not sure Rick's solution is what was intended in K&R. I believe the second argument ought to be a string and not a char.
Pilcrow's solution seems right. But in the outer loop is can start from ls-lt rather than ls-1 and in the inner loop you don't 
really need a third variable is2
Adam's solution is also correct. But it would be better to start from the end of the source string and stop when a match is found,
rather than starting from the beginning and keep on going as long as possible. */

#include <stdio.h>
#include <string.h>

int strrindex(char *s, char *t)
{
	int i, j, flag, slen = strlen(s), tlen = strlen(t);
	for(i = slen - tlen; i >= 0; i--)
	{
		flag = 1;
		for(j = i; j < i + tlen; j++)
		{
			if(s[j] != t[j-i])
			{
				flag = 0;
				break;
			}
		}
		if(flag == 1)
			return i;
	}
	return -1;
}

int main()
{
	char s[] = "When I get older, I will be stronger";
	char t[] = "I";
	printf("%d\n", strrindex(s, t));
	return 0;
}

Solution by Liangming

/* I just changed a little bit from the original version of the textbook.
 * I suppose that the question asks for two parameters which are both strings.
*/

#include <stdio.h>
#define MAXLINE 1000 /* maximum input line length */

int getline(char line[], int max);
int strindex(char source[], char searchfor[]);

char pattern[] = "ould";    /* pattern to search for */

/* find all lines matching pattern */
int main()
{
    char line[MAXLINE];
    int found = 0;
    int p;

    while (getline(line, MAXLINE) > 0)
        if ((p = strindex(line, pattern)) >= 0) {
            printf("%d\n", p);
            printf("%s", line);
            found++;
        }

    return found;
}

/* getline: get line into s, return length */
int getline(char s[], int lim)
{
    int c, i;

    i = 0;
    while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
        s[i++] = c;
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

/* strindex: return the position of the rightmost occurrence of t in s, -1 if none */
int strindex(char s[], char t[])
{
    int i, j, k;
    int p = -1;

    for (i = 0; s[i] != '\0'; i++) {
        for (j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++)
            ;
        if (k > 0 && t[k] == '\0') {
            p = i;
            i += k - 1;
        }
    }

    return p;
}

Solution by Luke Panayi

My approach involved iterating backwards through the line, as well as checking the pattern in verse too by taking it's length. Stops at first match.

/*
  Write the function strrindex(s,t), which returns the position
  of the rightmost occurrence of t in s, or -1 if there is none.
 */

#include <stdio.h>
#define BUFFER 1000

char pattern[] = "ould";

int main()	{
  char line[BUFFER];
  int len, pos, found = 0;

  while ((len=getline(line, BUFFER)) > 0)	{
    if ((pos=strindex(line, pattern, len))>= 0)	{
      printf("At position %d: %s",pos, line);
    found++;
    }
  }
  return found;
}

int getline(char s[], int lim)	{
	int c, i;

  i = 0;
  while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
    s[i++] = c;
  if (c == '\n')
    s[i++] = c;
  s[i] = '\0';
  return i;
}

int strindex(char s[], char t[], int len)	{
  int i,j,k,l;

  for (l=0; t[l] != '\0'; ++l);

  for (i=len; i >= 0; --i)	{
    for (j=i, k=0; t[k] != '\0' && s[j] == t[l-k-1]; --j, ++k); //transverse pattern array backwards, -1 to skip null char
    if (k > 0 && t[k] == '\0')	{
      return j+1;
    }
  }
  return -1;

}

Solution by Miguel Degrossoli

/* Exercise 4-1. Write the function strindex(s,t) which returns the position of
 * the rightmost occurrence of t in s, or -1 if there's none. */

#include <stdlib.h>
#include <stdio.h>

#define MAXLEN	1000	/* maximum number of characters in a line */

#define	ERRNONE		0	/* no error */
#define ERREMPTY	1	/* string is empty */

int mygetline(char s[], unsigned maxl);
int strindex(char s[], char t[]);

/* main: search for a string in a given text */
int main()
{
	char s[MAXLEN + 1], t[MAXLEN + 1];
	int i;

	printf("Search for: ");
	if (mygetline(t, MAXLEN) == 0)
	{
		printf("Cannot search for an empty string.\n");
		exit(ERREMPTY);
	}

	printf("Look into:\n");
	while (mygetline(s, MAXLEN) > 0)
		if ((i = strindex(s, t)) >= 0)
			printf("\"%s\", index %d.\n", s, i);

	exit(ERRNONE);
}

/* mygetline: fills s until EOF, \n or it reaches maxl, returns the length of
 * s */
int mygetline(char s[], unsigned maxl)
{
	unsigned char c;
	int i = 0;

	while (i <= maxl && (c = getchar()) != EOF && c != '\n')
		s[i++] = c;

	s[i] = '\0';

	return i;
}

/* strindex: searches for the last occurrence of t in s */
int strindex(char s[], char t[])
{
	int i, j, n, found = 0;

	for (i = 0; s[i] != '\0'; i++)
		;

	for (j = 0, n = 0; t[j] != '\0'; j++, n++)
		;

	for (; i >= 0; i--)
	{
		for (j = n - 1; j >= 0 && s[i] == t[j] && i-- >= 0; j--)
			;
		if (j <= 0)
			return ++i;
	}

	return -1;
}

Solution by anonymous

My solution involves an exact clone of page 69 with the below changes to strindex (now called strrindex). My change has it start i at the last char in s and search from right to left until t is found. The original code had i start at 0 and search left to right until t is found.

// original code
for (i = 0; s[i] != '\0'; i++)
// my code which replaced the above line with these four lines:
i = 0;
while (s[i] != '\0')
    i++;
while (--i >= 0)

My change implements the strlen(s) function by setting i to equal the index of '\0' in s. That way i equals strlen(s) when it gets to the while loop. Then I start the while loop off at --i so we don't search a match of '\0'. The rest of the code is the same on page 69. This is the full code just in case someone wants it.

#include <stdio.h>

/*
    Exercise 4-1. Write the function strrindex(s, t), which returns the position of the rightmost occurrence of t in s, or -1 if there is none.
*/

#define MAXLINE 1000 // maximum input line length

int getline(char line[], int max);
int strrindex(char source[], char searchfor[]);

char pattern[] = "ould"; // pattern to search for

// find all lines matching pattern
int main()
{
    char line[MAXLINE];
    int found= 0;
    
    while (getline(line, MAXLINE) > 0)
        if (strrindex(line, pattern) >= 0)
        {
            printf("%s", line);
            found++;
        }
    return found;
}

// get line into s, return length
int getline(char s[], int lim)
{
    int c, i;
    i = 0;
    while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
        s[i++] = c;
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

// return index of t in s, -1 if none
// searches from right to left (reversed)
int strrindex(char s[], char t[])
{
    int i, j, k;

    i = 0;
    while (s[i] != '\0')
        i++;

    while (--i >= 0) // s[i] starts out at '\0' so --i in while condition is ideal to skip it
    {
        for (j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++)
            ;
        if (k > 0 && t[k] == '\0')
            return i;
    }
    return -1;
}

From clc-wiki

Contents

Solution by Rick Dearman

Solution by Xggggg

Solution by Pilcrow

Solution by Adam89

Solution by menonsahab

Solution by Liangming

Solution by Luke Panayi

Solution by Miguel Degrossoli

Solution by anonymous

Views

Personal tools

Site_logo

Search

Content_hierarchy

Tools