门户网站 建设方案,专业团队照片,房屋设计平面图效果图,wordpress load-scripts.php声明#xff1a;下边的例子均表示下标从1开始的数组
ne数组的定义#xff1a;
next[i] 就是使子串 s[1…i] 有最长相等前后缀的前缀的最后一位的下标。ne[i]也可以表示相等子串的长度
准备执行jne[j]时#xff0c; 表示当前s[i]!p[j1] , 如果ne[j]1 #xff0c;那么下…声明下边的例子均表示下标从1开始的数组
ne数组的定义
next[i] 就是使子串 s[1…i] 有最长相等前后缀的前缀的最后一位的下标。ne[i]也可以表示相等子串的长度
准备执行jne[j]时 表示当前s[i]!p[j1] , 如果ne[j]1 那么下一次匹配从p数组的第二个字符也就是p[j1]开始比较是否s[i]p[j 1]
a b a b a b c a b
1 2 3 4 5 6 7 8 9 a b a b a b c a b 1 2 3 4 5 6 7 8 9
同理ne数组的建立也是这样的从数组的第二个字符开始枚举因为第一个字符没有相同的字串从i2,j0开始枚举
i2,j0 p[i] ! p[j1] ne[2]0;
i3,j0 p[i]p[j1] ,j,ne[3]1;
i4,j1 p[i]p[j1] ,j,ne[4]2;
i5,j2 p[i]p[j1] ,j,ne[5]3;
i6,j3 p[i]p[j1] ,j,ne[6]4;
i7,j4 p[i]!p[j1] (此时两者不相等那么执行jne[j] ,j2,刚才想样例时发现为什么下一次比较不直接比较j15,i7呢想了一下其实这和在s数组中和p数组相等的字串问题一样此时p数组才走到j4那么 j 退一下只能退到 j ne[i] 发现p[i]!p[j1]继续执行jne[j] ,j0所以下一次比较就从0开始比较
其实直接看ne数组的更新比较绕可以对比s数组和p数组的匹配两者其实是一样的就上边最后一步 j ----- 0来说下一次s数组的s[i]要和p数组的p[1]比较 KMP数组的应用 分析观察样例发现每次后边加的都是剔除字符串t的最长的前缀和后缀相等的子串后剩下的字符串那么就可以用KMP求最长字串的长度也就是 ne[n]
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 55;int n, m;
char str[N];
int ne[N];int main()
{scanf(%d%d, n, m);scanf(%s, str 1);for (int i 2, j 0; i n; i ){while (j str[i] ! str[j 1]) j ne[j];if (str[i] str[j 1]) j ;ne[i] j;}// coutne[n]endl;printf(%s, str 1);for (int i 0; i m - 1; i )printf(%s, str 1 ne[n]);return 0;
}
