#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> NextArray(const string& matchStr) {
    vector<int> next(256, -1); // 初始化一个大小为256的数组，初始值为-1
    for (int i = 0; i < matchStr.size(); ++i) {
        next[(int)matchStr[i]] = i; // 记录每个字符最后一次出现的位置
    }
    return next;
}

int sundyStr(const string& str, const string& matchStr) {
    int strLen = str.size();
    int matchLen = matchStr.size();
    if (strLen < matchLen || strLen == 0 || matchLen == 0) return -1; // 如果主串比匹配串短，或者任一串为空，直接返回-1

    vector<int> next = NextArray(matchStr); // 预处理匹配串，生成next数组

    int i = 0; // 主串的起始匹配位置
    while (i <= strLen - matchLen) {
        int j = 0;
        while (j < matchLen && str[i + j] == matchStr[j]) {
            ++j;
        }
        if (j == matchLen) {
            return i; // 匹配成功，返回匹配的起始位置
        }

        // 匹配失败，根据next数组移动模式串
        if (i + matchLen >= strLen) {
            break; // 如果已经到达主串末尾，退出循环
        }
        int shift = matchLen - next[(int)str[i + matchLen]];
        i += shift;
    }

    return -1; // 匹配失败，返回-1
}

int main() {
    string str = "wonwondowananowandewonderowo";
    string matchStr = "wondero";
    int state = sundyStr(str, matchStr);
    if (state != -1) {
        cout << "匹配成功，目标串首次出现于 源串的 [" << state << "] 位置" << endl;
    }
    else {
        cout << "匹配失败，源串不包含目标串！" << endl;
    }
    return 0;
}