首页 > 其他分享 >KMP

KMP

时间：2024-10-19 10:32:27浏览次数：6  
标签：TreeNode val int nullptr next KMP root

KMP

s1 字符串是否包含 s2 字符串，如果包含返回 s1 中包含 s2 的最左开头位置，不包含返回 -1

暴力方法就是 s1 的每个位置都做开头，然后去匹配 s2 整体，时间复杂度 O(n * m)

KMP 算法可以做到时间复杂度 O(n + m)

28. 找出字符串中第一个匹配项的下标

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // next 数组：规定 next[0] = -1
    // 其他位置 next[i] = a 表示 p[0, i-1] 子串的真前缀和真后缀的最大匹配长度（即前后缀不包含整个子串）为 a
    vector<int> getNextArr(string &p) {
        int m = p.length();
        if (m == 1) return {-1};
        vector<int> next(m);
        // 起始位置规定为 -1
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        // 前面子串中和当前位置进行对比的位置
        int pre = 0;
        while (i < m) {
            if (p[i - 1] == p[pre]) {
                next[i++] = ++pre;
            } else if (pre > 0) {
                // 往前跳
                pre = next[pre];
            } else {
                next[i++] = 0;
            }
        }

        return next;
    }

    // 时间复杂度 O(n + m)
    int kmp(string &s, string &p) {
        int n = s.length();
        int m = p.length();
        // 时间复杂度 O(m)
        vector<int> next = getNextArr(p);

        // 字符串 s 当前匹配位置
        int i = 0;
        // 模式串 p 当前匹配位置
        int j = 0;
        // 时间复杂度 O(n)
        while (i < n && j < m) {
            if (s[i] == p[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = next[j];
            }
        }
        return j == m ? i - m : -1;
    }

    int strStr(string haystack, string needle) {
        return kmp(haystack, needle);
    }
};

572. 另一棵树的子树

  • 暴力递归
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 判断两棵树是否完全一样
    bool isSame(TreeNode *r1, TreeNode *r2) {
        if (r1 == nullptr && r2 == nullptr) return true;
        if (r1 == nullptr || r2 == nullptr) return false;
        return r1->val == r2->val && isSame(r1->left, r2->left) && isSame(r1->right, r2->right);
    }

    // 时间复杂度 O(n * m)
    bool isSubtree(TreeNode *root, TreeNode *subRoot) {
        if (root != nullptr && subRoot != nullptr)
            return isSame(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
        return subRoot == nullptr;
    }
};
  • 先序序列化（遇到空节点要记录） + KMP
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // next 数组：规定 next[0] = -1
    // 其他位置 next[i] = a 表示 p[0, i-1] 子串的真前缀和真后缀的最大匹配长度（即前后缀不包含整个子串）为 a
    vector<int> getNextArr(vector<string> &p) {
        int m = p.size();
        if (m == 1) return {-1};
        vector<int> next(m);
        // 起始位置规定为 -1
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        // 前面子串中和当前位置进行对比的位置
        int pre = 0;
        while (i < m) {
            if (p[i - 1] == p[pre]) {
                next[i++] = ++pre;
            } else if (pre > 0) {
                // 往前跳
                pre = next[pre];
            } else {
                next[i++] = 0;
            }
        }

        return next;
    }

    // 时间复杂度 O(n + m)
    int kmp(vector<string> &s, vector<string> &p) {
        int n = s.size();
        int m = p.size();
        // 时间复杂度 O(m)
        vector<int> next = getNextArr(p);

        // 字符串 s 当前匹配位置
        int i = 0;
        // 模式串 p 当前匹配位置
        int j = 0;
        // 时间复杂度 O(n)
        while (i < n && j < m) {
            if (s[i] == p[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = next[j];
            }
        }
        return j == m ? i - m : -1;
    }

    // 中序序列化，空节点也记录
    void serial(TreeNode *root, vector<string> &path) {
        if (root == nullptr) {
            path.emplace_back("null");
            return;
        }
        path.emplace_back(to_string(root->val));
        serial(root->left, path);
        serial(root->right, path);
    }

    // 时间复杂度 O(n * m)
    bool isSubtree(TreeNode *root, TreeNode *subRoot) {
        vector<string> s;
        vector<string> p;
        serial(root, s);
        serial(subRoot, p);
        return kmp(s, p) != -1;
    }
};

P4391 [BOI2009] Radio Transmission 无线传输

#include <iostream>
#include <vector>

using namespace std;

vector<int> getNextArr(string s) {
    int n = s.size();
    // 多求了一位
    vector<int> next(n + 1);
    next[0] = -1;
    next[1] = 0;
    int i = 2, pre = 0;
    while (i <= n) {
        if (s[i - 1] == s[pre]) {
            next[i++] = ++pre;
        } else if (pre > 0) {
            pre = next[pre];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<int> next = getNextArr(s);
    cout << n - next[n];
}

P4824 [USACO15FEB] Censoring S

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int MAXN = 1000001;
vector<int> nxt(1000001);
// <s 中的位置 i，t 中与 s[i] 匹配的位置>
vector<pair<int, int>> stk(MAXN);
// 栈顶位置
int top;

void generateNxt(string s) {
    nxt[0] = -1;
    int n = s.size();
    if (n == 1) return;
    nxt[1] = 0;
    int i = 2, pre = 0;
    while (i < n) {
        if (s[i - 1] == s[pre]) {
            nxt[i++] = ++pre;
        } else if (pre > 0) {
            pre = nxt[pre];
        } else {
            nxt[i++] = 0;
        }
    }
}

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int m = t.length();

    top = 0;
    generateNxt(t);

    int i = 0, j = 0;
    while (i < n) {
        if (s[i] == t[j]) {
            stk[top++] = make_pair(i, j);
            i++;
            j++;
        } else if (j == 0) {
            stk[top++] = make_pair(i, -1);
            i++;
        } else {
            j = nxt[j];
        }
        if (j == m) {
            // 弹出一个字符串 t
            top -= m;
            // 如果栈非空，栈顶 s[stk[top - 1].first] 当前和 t[stk[top - 1].second] 匹配，就从下一位置继续和 i 对比
            // 如果栈空，就从 t 的起始位置继续和 i 对比
            j = top > 0 ? stk[top - 1].second + 1 : 0;
        }
    }

    string res = "";
    // 输出栈中剩下的字符
    for (int k = 0; k < top; ++k)
        res += s[stk[k].first];
    cout << res;
}

1367. 二叉树中的链表

  • 递归
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 判断是否能从当前节点匹配全部链表
    bool dfsJudge(struct TreeNode *root, struct ListNode *head) {
        if (head == nullptr) return true;
        if (root == nullptr || root->val != head->val) return false;
        return dfsJudge(root->left, head->next) || dfsJudge(root->right, head->next);
    }

    // 遍历二叉树
    bool dfs(struct TreeNode *root, struct ListNode *head) {
        if (root == nullptr) return false;
        if (dfsJudge(root, head)) return true;
        return dfs(root->left, head) || dfs(root->right, head);
    }

    bool isSubPath(ListNode *head, TreeNode *root) {
        return dfs(root, head);
    }
};
  • KMP
#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    void generateNext(ListNode *head, vector<int> &list, vector<int> &next) {
        // 链表转成数组
        while (head != nullptr) {
            list.emplace_back(head->val);
            head = head->next;
        }
        int n = list.size();
        // 生成 list 数组的 next 数组
        next.resize(n);
        next[0] = -1;
        if (n == 1) return;
        next[1] = 0;
        int i = 2, pre = 0;
        while (i < n) {
            if (list[i - 1] == list[pre]) {
                next[i++] = ++pre;
            } else if (pre > 0) {
                pre = next[pre];
            } else {
                next[i++] = 0;
            }
        }
    }

    // 从 list[cur] 和 root.val 开始往下对比，返回能否将 list 全部匹配
    bool dfs(vector<int> &list, vector<int> &next, TreeNode *root, int cur) {
        if (cur == list.size()) return true;
        if (root == nullptr) return false;
        // 失配时，找到上一个匹配的位置
        // 均摊下来，时间复杂度 O(1)
        while (cur >= 0 && root->val != list[cur])
            cur = next[cur];
        // 推出循环时，i == -1 或者 i >=0 （匹配上了）
        // 子树从下个位置 list[cur + 1] 对比
        return dfs(list, next, root->left, cur + 1) || dfs(list, next, root->right, cur + 1);
    }

    // 时间复杂度 O(n + m)
    bool isSubPath(ListNode *head, TreeNode *root) {
        vector<int> list;
        vector<int> next;
        generateNext(head, list, next);
        return dfs(list, next, root, 0);
    }
};

1397. 找到所有好字符串

// todo 数位DP

标签：TreeNode,val,int,nullptr,next,KMP,root
From： https://www.cnblogs.com/sprinining/p/18475570

相关文章

  • KMP
    一个kmp学了\(n\)遍终于学懂的屑菜bot。下文默认文本串为\(s\)，模式串为\(t\)。前缀函数定义\(\pi_i\)表示前缀为\(i\)的子串中的最长公共前后缀（border）长度。不难发现，将文本串接在模式串后，中间隔一个特殊字符，若出现\(\pi_i=|t|\)的情况则说明匹配成功了。求取......
  • Z函数（扩展KMP）
    扩展KMP（Z函数）Z数组简单理解\(Z[i]\)表示字符串从i出发，与整体相比有多长的公共前缀aaabaac7210210可以先理解马拉车再来看首先，设置两个类似的东西，关键点\(c\)和最右边界\(r\)，表示\(Z[c]\)是目前所有\(Z\)中，\(i+Z[i]\)最右边的那个对于： r01......
  • 对KMP算法的疑问与理解
    对KMP算法的疑问与理解核心:在逐字符遍历主串与模式串的过程中，发生失配时，不回溯主串的i字符指针，而是通过确定已经匹配过的模式串的子串的前缀集合与后缀集合的交集中最长元素的长度，来移动模式串的j字符指针，实现模式串的整体向右滑动，跳过绝不可能发生的字符串匹配,以此实现......
  • [NOI2014] 动物园——KMP 倍增
    [NOI2014]动物园题目描述近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解KMP算法。园长：“对于一个字符串\(S\)，它......
  • kmp算法模板
    voidkmp(){n=strlen(s+1);//s是目标串m=strlen(p+1);//p是模板串//nxt预处理开始intj=0;nxt[1]=0;for(inti=2;i<=m;i++){while(j>0&&p[j+1]!=p[i])/*判断当前子串的前后缀相等的长度是否能增......
  • KMP循环节
    KMP循环节在icpc2019ChinaCollegiateProgrammingContestQinhuangdaoOnsiteJ.MUVLUVEXTRA由题易得，要求这个数的小数部分的\(S=a×循环长度−b×循环节的长度\),让这个S尽可能的大。又因为对于循环长度我们可以用kmp算法来求出最小循环节，所以我们可以枚举循环长度......
  • 洛谷题单指南-字符串-P3375 【模板】KMP
    原题链接：https://www.luogu.com.cn/problem/P3375题意解读：给定两个字符串：原串s，模式串p，求p在s中出现的所有位置，并输出p的长度为1~p.size()的子串的最长相同真前、后缀的长度。解题思路：KMP模版题，分两问，第一问通过KMP核心算法实现，第二问输出模式串的Next数组内容，接下来一一解读。......
  • KMP算法
    引言之前在打ACM竞赛时就学过一些字符串相关的算法，其中就包括KMP。但是面向竞赛的KMP算法和面向408的KMP算法在一些概念和实现细节上有细微差异，所以特意写了这篇文章对408中的KMP算法做出总结字符串的前缀、后缀和部分匹配指前缀指除了最后一个字符以外，字符串的所有头部子串；后......
  • 8592 KMP算法
    首先，我们需要理解KMP算法的基本思想。KMP算法是一种改进的字符串匹配算法，它的主要思想是利用已经部分匹配的这个有效信息，使得后续的匹配中，尽量减少字符串的回溯，提高匹配效率。KMP算法的关键在于通过一个next数组，保存模式串中前后缀的最长的共有元素的长度。当模式串中的字符......
  • 字符串从入门到退竞（2）——KMP 算法
    约定在文字描述中字符串下标从\(1\)开始，代码中从\(0\)开始。前缀函数对于长\(n\)的字符串\(S\)，其前缀函数是一个长\(n\)的数组（数列）\(\pi\)，定义如下：若\(S[1..i]\)有相等的真前缀和真后缀（称之为border），\(\pi[i]\)为其长度的最大值；若不存在，\(\pi[i]=0\)。字符串的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99