//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "KMP": {
        "prefix": "acm-6.1kmp",
        "body": [
            "// KMP算法：构建next数组",
            "vector<int> buildNext(const string& pattern) {",
            "    int n = pattern.size();",
            "    vector<int> next(n, 0);",
            "    int j = 0;",
            "    for (int i = 1; i < n; ++i) {",
            "        while (j > 0 && pattern[i] != pattern[j]) {",
            "            j = next[j - 1];",
            "        }",
            "        if (pattern[i] == pattern[j]) {",
            "            j++;",
            "        }",
            "        next[i] = j;",
            "    }",
            "    return next;",
            "}",
            "",
            "// KMP算法：在文本中查找模式串，返回所有匹配的起始位置",
            "vector<int> kmpSearch(const string& text, const string& pattern) {",
            "    vector<int> result;",
            "    int n = text.size();",
            "    int m = pattern.size();",
            "    if (m == 0) return result;",
            "    ",
            "    vector<int> next = buildNext(pattern);",
            "    int j = 0;",
            "    for (int i = 0; i < n; ++i) {",
            "        while (j > 0 && text[i] != pattern[j]) {",
            "            j = next[j - 1];",
            "        }",
            "        if (text[i] == pattern[j]) {",
            "            j++;",
            "        }",
            "        if (j == m) {",
            "            result.push_back(i - m + 1);",
            "            j = next[j - 1];",
            "        }",
            "    }",
            "    return result;",
            "}"
        ],
        "description": "插入 KMP"
    }
}