传统的网站开发模式和mvc,网站导航栏垂直,北京推广营销,常德网站优化题目链接 题目大意就是给你两个字符串#xff0c;求出第一个字符串在第二个字符串中出现的次数。
如果我们暴力匹配的话#xff0c;复杂度是 len(first) * len(second) 对于题目给的 1e4 * 1e6 显然暴力不可取#xff0c; 这里就用到 KMP 。
说到 KMP 最难理解的就是 next…题目链接 题目大意就是给你两个字符串求出第一个字符串在第二个字符串中出现的次数。
如果我们暴力匹配的话复杂度是 len(first) * len(second) 对于题目给的 1e4 * 1e6 显然暴力不可取 这里就用到 KMP 。
说到 KMP 最难理解的就是 next 数组了下面给出了 next 数组的详细求法。
我们先预设两个指针一个指向 i 0 一个指向 j -1 .应为两个值如果设置成一样那么对应的字母一定也是一样的就完成不了我们想要的任务了。 从第一项开始我们默认他是匹配的应为next数组的第一项就是 -1(当然这里数组下标是从0开始的)。默认他是匹配的实际上这是一个边界条件我们进行next[i] j; 接下来我们i 1 1 j 1 0我们有其对应的字母不一样我们进行 j next[j]知道又是匹配的我们进行next[i] j, 以此重复得到整个next数组。
实际上nex数组的表示意义就是这个点的前面的字符串能够匹配的数组的最后一个下标
#includeiostream
#includealgorithm
#includecstring
#includecstdio
using namespace std;
const int N1 1e4 10, N2 1e6 10;
char fir[N1], sec[N2];
int nex[N1];
void getnex() {int i 0, j -1, n strlen(fir);while(i n) {if(j -1 || fir[i] fir[j]) nex[i] j;else j nex[j];}
}
int kmp() {int ans 0;int i 0, j -1, lf strlen(fir), ls strlen(sec);while(i ls) {if(j -1 || fir[j] sec[i]) i, j;else j nex[j];if(j lf) ans, j -1;}return ans;
}
int main() {int t;scanf(%d, t);while(t--) {scanf(%s %s, fir, sec);nex[0] -1;getnex();printf(%d\n, kmp());}return 0;
}
