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.
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; }
