bool RideShare::kmpStringAlgorithm(const string total,const string partial) { //Algorithm for exact string search

	int m = partial.length();
	int n = total.length();
	int pi[m];

	computePrefixFunction(partial, pi);

	int i = 0;  // index for total[] string
	int j = 0;  // index for partial[] string
	while (i < n) {

		if (tolower(partial[j]) == tolower(total[i])){ //case insensitive    o codigo ASCII das minusculas é o das maiusculas + 32

			j++;
			i++;
		}

		if (j == m) {

			return true;
		}

		// mismatch after j matches
		else if (i < n && tolower(partial[j]) != tolower(total[i])) {
			if (j != 0)
				j = pi[j - 1];
			else
				i = i + 1;
		}
	}
	return false;
}

void RideShare::computePrefixFunction(string partial, int *pi) {

	int m = partial.length();
	// length of the previous longest prefix suffix
	int len = 0;

	pi[0] = 0; // lps[0] is always 0

	// the loop calculates lps[i] for i = 1 to M-1
	int i = 1;
	while (i < m) {
		if (tolower(partial[i]) == tolower(partial[len])) {
			len++;
			pi[i] = len;
			i++;
		} else // (pat[i] != pat[len])
		{
			// This is tricky. Consider the example.
			// AAACAAAA and i = 7. The idea is similar
			// to search step.
			if (len != 0) {
				len = pi[len - 1];

				// Also, note that we do not increment
				// i here
			} else // if (len == 0)
			{
				pi[i] = 0;
				i++;
			}
		}
	}
}


bool RideShare::editDistanceAlgorithm(string pat, string txt){

	int n = txt.length();
	int m = pat.length();
	int after, before;
	int d[n+1];

	for (int i = 0; i < n + 1; i++) {

		d[i] = i;
	}

	for (int i = 1; i < m + 1; i++) {

		before = d[0];
		d[0] = i;

		for(int k = 1; k < n+1; k++){

			if(pat[i - 1] == txt[k - 1]){

				after = before;
			} else{

				after = min(before, d[k]);
				after = 1 + min(after, d[k-1]);
			}

			before = d[k];
			d[k] = after;
		}
	}

	//return d[n];
	float txtLength = txt.length();
	float edalgValue = ((float)d[n]) / txtLength;
	if(edalgValue <= 0.70)
		return true;
	else
		return false;
}