首页 > 代码库 > HDU 2087 (KMP不可重叠的匹配) 花布条
HDU 2087 (KMP不可重叠的匹配) 花布条
题意：
用两个字符串分别表示布条和图案，问能从该布条上剪出多少这样的图案。
分析：
毫无疑问这也是用KMP匹配，关键是一次匹配完成后，模式串应该向后滑动多少。
和上一题 HDU 1686 不同，两个图案肯定不能在母串中有交叉的部分，所以当匹配成功一次后，应当滑动整个模式串的长度。
和上一题比，代码几乎不变，只是
j = next[j]; 变为 j = 0;
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 1000 + 10; 5 char p[maxn], q[maxn]; 6 int next[maxn]; 7 8 void get_next(char* p, int l) 9 {10 int j = 0, k = -1;11 next[0] = -1;12 while(j < l)13 {14 if(k == -1 || p[k] == p[j])15 {16 k++;17 j++;18 next[j] = k;19 }20 else k = next[k];21 }22 }23 24 int KMP(char* p, int lenp, char* q, int lenq)25 {26 int i = 0, j = 0, ans = 0;27 while(i < lenp)28 {29 if(j == -1 || p[i] == q[j])30 {31 i++;32 j++;33 }34 else j = next[j];35 if(j == lenq)36 {37 ans++;38 j = 0;39 }40 }41 return ans;42 }43 44 int main(void)45 {46 //freopen("2087in.txt", "r", stdin);47 48 while(scanf("%s", p) == 1)49 {50 if(p[0] == ‘#‘) break;51 52 memset(next, 0, sizeof(next));53 scanf("%s", q);54 int lenp = strlen(p);55 int lenq = strlen(q);56 get_next(q, lenq);57 printf("%d\n", KMP(p, lenp, q, lenq));58 }59 60 return 0;61 }
HDU 2087 (KMP不可重叠的匹配) 花布条
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。