indexOf ()

Write a recursive function named indexOf that accepts two strings s1 and s2 as parameters and that returns the starting index of the first occurrence of the second string s2 inside the first string s1, or -1 if s2 is not found in s1. The table below shows several calls to your function and their expected return values. If s2 is the empty string, always return 0 regardless of the contents of s1. If s2 is longer than s1, it of course cannot be contained in s1 and therefore your function would return -1 in such a case. Notice that case matters; the last example returns -1.

CallValue Returned

indexOf("Barack Obama", "Bar")	0
indexOf("foo", "foo")	0
indexOf("Stanford CS", "ford")	4
indexOf("Barack Obama", "ack")	3
indexOf("Barack Obama", "a")	1
indexOf("sandwich", "")	0
indexOf("Barack Obama", "McCain")	-1
indexOf("Barack Obama", "ACK")	-1

Constraints: Your solution must obey the following constraints:

• Your solution must not use any loops; it must be recursive.
• Strings have member functions named find and rfind, but you should not call them, because they allow you to get around using recursion. Similarly, the replace member is forbidden. You should limit yourself to using only the following string members:
  • at, append, compare, erase, insert, length or size, substr, trim, operators such as [], ==, !=, <, etc.
• Do not construct any data structures (no array, vector, set, map, etc.), and do not declare any global variables. You are allowed to define other "helper" functions if you like.

자료구조를 사용하지 못하기 때문에 배열을 대신할 다른 방법을 생각해야 했다. 

재귀함수에 사용이 가능하기 때문에 재귀를 활용해서 풀어보았다.

using namespace std;

int indexOfHelper(string s1, string s2, int start_index)
{
	if (s2.empty())return 0;	// found as it starts
	if (start_index + s2.size() > s1.size()) return -1;	// not matched

	if (s1.substr(start_index, s2.size()) == s2) return start_index;

	return indexOfHelper(s1, s2, start_index + 1);
}

int indexOf(string s1, string s2)
{
	return indexOfHelper(s1, s2, 0);
}

재귀함수를 도와줄 함수를 만들어서 재귀함수에 인덱스를 계산하는 함수를 추가해 주었다. indexof 함수에 인자값은 정해져 있기 때문에 추가해 주었다.

indexofHelper 함수를 보면 두 개의 문자열과 하나의 정수값을 받는다.

만약 s2 가 어떠한 입력도 들어갖 않은 상태 즉 "" 인 상태면 0을 리턴한다.

만약 찾고자 하는 (s2)에 길이가 s1보다 길다면 만족하지 못하는 값이므로 -1을 리턴한다.

substr을 사용해서 startindex 부터 s2의 길이 만큼에 문장을 갖고 온다 그리고 이를 찾고자 하는 문장(s2)과 비교하여 같은지 비교를 한다. 같다면 현재 인덱스 번호 start_index를 리턴한다.

모든 조건을 만족하지 못 했다면 재귀를 하는데 이때 시작 인덱스를 하나 늘려준다.