首页 > 【模板】KMP字符串匹配
开通博客写题解
头像 我需要专注
发表于 2025-12-05 13:36:13
#include <bits/stdc++.h> using namespace std; const int N=1000010; char s[N],p[N]; int ne[N]; int main() 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 WangYanYo
发表于 2023-05-22 22:18:24
第二题题解： 首先长字符串肯定不是短字符串的子串。所以先找到最短的的那个字符串，设为a，所有长于a的字符串的结果都是0。 还剩下和a同样长的字符串，他们与a的关系只有相等和不等两种，那么就发现一个性质： 如果存在一个字符串s，a不是s的子串，那么所有字符串的结果都是0。对于和a同样长 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Z_L_G
发表于 2025-03-20 14:52:25
功能 在主串中查找子串，返回头位置(0开头索引) 复杂度 n,m为主串和子串长度 思路 把主串和子串拼接到一起，中间隔开，记为合并串s 对s中的每一个子串计算其最长匹配真前后缀长度，如果有某一个字串的最长匹配真前后缀长度等于子串长度，则说明查找到子串 对于每一个子串希望求他的最长匹配真前 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”