毕节做网站的公司,省建设信息中心查询,网站建设与管理适合男的还是女的,网站开发ceil(5.5)KMP算法 KMP算法是一种字符串匹配算法#xff0c;用于匹配模式串P在文本串S中出现的所有位置。 例如S“ababac#xff0c;P“aba”#xff0c;那么出现的所有位置是13。 在初学KMP时#xff0c;我们只需要记住和学会使用模板即可#xff0c;对其原理只需简单理解#xff…KMP算法 KMP算法是一种字符串匹配算法用于匹配模式串P在文本串S中出现的所有位置。 例如S“ababacP“aba”那么出现的所有位置是13。 在初学KMP时我们只需要记住和学会使用模板即可对其原理只需简单理解不要过度深究避免把自己绕进去可以课后自己慢慢去画图理解。 KMP算法将原本On2的字符串匹配算法优化到了On.其精髓在于next数组next数组表示此时模式串下标失配时应该移动到的位置也表示最长的相同真前后缀的长度。 例如P“ababac”S“abababac”。 当匹配到i6j5Pi1Si时j不会移动到1重新开始匹配而是移动到nexj3继续匹配 则接下来i6j3有Pj1Si成功匹配则ij继续后移直到i8.j6完成一次匹配则P在S中第一次出现的位置为j-i13。 计算next数组next数组仅与模式串P有关的方式就是用P自己去匹配自己大家只需要掌握模板即可暂时不要深究其原理。
char s[N],p[N];
int nex[M];
int n strlen(s1),mstrlen(p1);//字符串下标从 1 开始
nex[0]nex[1]0;
for(int i2,j0;im;i){while(jp[i]!p[j1])jnex[j];if(p[i]p[j1])j;//从 while 出来后要么 j0要么 p[i]p[j1]如果匹配成果则 j 后移nex[i]j;//如果匹配失败就回到 j因为此时 p[1~j]p[i-j1~j]或 j0回到最初的地方开始匹配
}通过 next 数组匹配
for(int i1,j0;in;i)
{while(js[i]!p[j1])jnex[j];if(s[i]p[j1])j;if(jm)//成功匹配一次
}斤斤计较的小Z 思路KMP 算法模板不知道为啥结果不对
#includebits/stdc.h
using namespace std;
const int N 20,M20;
char s[N],p[M];
int nex[M];int main(){scanf(%s\n%s,p1,s1);int nstrlen(s1),mstrlen(p1);nex[0]nex[1]0;for(int i2,j0;im;i){while(jp[j1]!p[i])jnex[j];if(p[j1]p[i])j;nex[i]j;}int res0;for(int i1,j0;in;i){while(jp[j1]!s[i])jnex[j];if(p[j1]s[i])j;if(jm)res;}coutres\n;return 0;
}boarder 思路利用 KMP 求整个串的最长真前后缀len-nex[len]就是整个串的循环节len 能整除循环节就是答案不能就是 1。
#includebits/stdc.h
using namespace std;
const int N1e610;
char p[N];
int nex[N];
int main( ){scanf(%s,p1);unsigned long mstrlen(p1);nex[0]nex[1]0;for(int i2,j0;im;i){while(jp[i]!p[j1])jnex[j];if(p[i]p[j1])j;nex[i]j;}int lenm-nex[m];if(m%len0){coutm/lenendl;}else{cout1endl;}return 0;
}
幸运字符串 思路求 nex 数组找最大值就是答案
#includebits/stdc.h
using namespace std;
const int N 2e510;
int n;
char p[N];
int nex[N];
int main( ){cinn;scanf(%s,p1);unsigned long mstrlen(p1);for(int i2,j0;im;i){while(jp[i]!p[j1])jnex[j];if(p[i]p[j1])j;nex[i]j;}int ans0;for(int i1;im;i)ansmax(ans,nex[i]);coutansendl;return 0;
}你也喜欢幸运字符串吗 思路动态规划KMP不会。
#include bits/stdc.h
#define ll long long
#define PI 3.1415926
using namespace std;
typedef pairint, int vt;
typedef pairvt, vt PII;
const int N 1e6 10;
const int M 2 * N;
const int mod 998244353;
const ll INF 0x3f3f3f3f3f3f3f3f;int ne[N];
string s;
int n;void solve()
{cin n;cin s;memset(ne, 0, sizeof ne);s s;for (int i 2, j 0; i n; i){while (j s[i] ! s[j 1])j ne[j];if (s[i] s[j 1])j;ne[i] j;}vectorll f(n 5);for (int i 1; i n; i)f[i] 1;for (int i n; i 1; i--)f[ne[i]] f[i];ll ans 0;// for(int i1;in;i)coutf[i]endl;for (int i 1; i n; i){if (ne[i] ! 0)ans f[ne[i]];}cout ans endl;
}signed main()
{ios::sync_with_stdio(false);/*多组案例初始化*/// int t;cint;while(t--)solve();
}
