#include <iostream>
#include <string>
#include <cctype>

using namespace std;

string to_lower(string s){
    unsigned long len = s.length();
    for(unsigned long k=0; k < len; k++){
        s[k] = tolower(s[k]);
    }
    return s;
}

bool end_checker(string sourcestr){
    long loc = to_lower(sourcestr).find("end");
    if(loc != -1){
        return true;
    }
    return false;
}

bool isValidSearchString(string searchString) {
    if (searchString.length() == 0) {
        return false;
    }
    char lastChar = searchString[searchString.length() - 1];
    return lastChar == '+' || lastChar == '.' || lastChar == '*' || searchString == "**";
}

bool source_check(string sentence) {
    unsigned long length = sentence.length();
    for (unsigned long i = 0; i < length;  i++){
        if (!((sentence.at(i) >= 48 && sentence.at(i) <= 57) || (sentence.at(i) >= 65 && sentence.at(i) <= 90) || (sentence.at(i) >= 97 && sentence.at(i) <= 122) || (sentence.at(i) == 32))){
            return false;
        }
    }
    return true;
}

void searchWithRule(string sourceString, string searchString) {
    char lastChar = searchString[searchString.length() - 1];
    long foundIndex = 0;
    searchString.pop_back();
    char second_lastChar = searchString[searchString.length() - 1];
    if(second_lastChar == '*')
        searchString.pop_back();
    
    while((foundIndex = sourceString.find(searchString, foundIndex)) != string::npos){
        string word;
        long wordStart = sourceString.rfind(' ', foundIndex);
        long wordEnd = sourceString.find(' ', foundIndex);
        // Search string ends with '+': The word must start with the search string.
        if (lastChar == '+') {
            char check = sourceString[foundIndex - 1];
            if(check == ' '){
                word = sourceString.substr(wordStart + 1, wordEnd - wordStart);
            }else if(wordStart == -1 && foundIndex == 0){
                word = sourceString.substr(0, wordEnd - wordStart);
            }
            // Search string ends with '.': The word ends with search string.
        } else if (lastChar == '.') {
            char check = sourceString[foundIndex + searchString.length()];
            if (check == ' ') {
                word = sourceString.substr(wordStart + 1,wordEnd - wordStart);
            }else if(check != '\0' && foundIndex == wordEnd - searchString.length()){
                word = sourceString.substr(0, wordEnd - wordStart);
            }
            // Search string ends with '*': The word that does not include the search string at the beginning and the end but may contain it in the middle.
        } else if (lastChar == '*' && second_lastChar != '*') {
            if (foundIndex != wordStart+1 && foundIndex != wordEnd-1 && wordStart != wordEnd && searchString != sourceString.substr(wordEnd-searchString.length(), searchString.length()) && searchString != sourceString.substr(wordStart+1, searchString.length()) ) {
                word = sourceString.substr(wordStart + 1, wordEnd - wordStart);
            }
            // Search string ends with '**': Any word containing the search string regardless of location.
        } else if (lastChar == '*' && second_lastChar == '*') {
            word = sourceString.substr(wordStart + 1, wordEnd - wordStart);
        }
        if (foundIndex != -1 && word.length() != 0) {
            cout << "index: " << foundIndex << " word: "<< word << endl;
            word = "";
        }
        foundIndex++;
    }
}

int main() {
    string sourceString, temp;
    bool stopper = false;
    
    while (!stopper) {
        cout << "Enter source string: ";
        getline(cin, temp);
        if (!source_check(temp))
            temp.clear();
        if (end_checker(temp))
            stopper = true;
        if(sourceString == ""){
            sourceString += temp;
        }else{
            sourceString += " " + temp;
        }
    }
    
    while (true) {
        string searchString;
        cout << "Enter search string: ";
        getline(cin, searchString);
        if (to_lower(searchString) == "quit") {
            return 0;
        }
        searchWithRule(sourceString, searchString);
    }
    
    return 0;
}