本文共 1049 字，大约阅读时间需要 3 分钟。
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
KMP模板，算得时候， 当j移到尾部时，res+1,j置为0,再继续。
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e3 + 10;int Next[MAXN];int lena, lenb;string a, b;void Get_Next(){ int i = 0; int k = -1; Next[i] = k; while (i < lenb) { if (k == -1 || b[k] == b[i]) { k++; i++; if (b[k] == b[i]) Next[i] = Next[k]; else Next[i] = k; } else k = Next[k]; }}int Kmp(){ int i = 0,j = 0; int res = 0; while (i < lena) { if (j == -1 || a[i] == b[j]) i++,j++; else j = Next[j]; if (j == lenb) { res++; j = 0; } } return res;}int main(){ while (cin >> a) { if (a[0] == '#') break; cin >> b; lena = (int)a.length(); lenb = (int)b.length(); memset(Next, 0, sizeof(Next)); Get_Next(); cout << Kmp() << endl; } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10505802.html