菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
245
0

HDU/HDOJ 2087 剪花布条

原创
05/13 14:22
阅读数 41536

KMP裸题

(极限5分钟A题)

 1 /**
 2     freopen("in.in", "r", stdin);
 3     freopen("my.out", "w", stdout);
 4 */
 5 //// /////////////////////////////
 6 #include <cstdio>
 7 #include <cstring>
 8 const int N = 1010;
 9 
10 int nex[N];
11 char s[N], p[N];
12 
13 int main() {
14     while(scanf("%s", s)) {
15         if(s[0] == '#') break;
16         scanf("%s", p);
17         int ans = 0;
18         nex[0] = 0;
19         for(int i = 1, j = 0; i < strlen(p); i++) {
20             while(j && p[i] != p[j]) {
21                 j = nex[j - 1];
22             }
23             if(p[i] == p[j]) j++;
24             nex[i] = j;
25         }
26         for(int i = 0, j = 0; i < strlen(s); i++) {
27             while(j && s[i] != p[j]) {
28                 j = nex[j - 1];
29             }
30             if(s[i] == p[j]) j++;
31             if(j == strlen(p)) {
32                 ans++;
33                 j = 0;
34             }
35         }
36         printf("%d\n", ans);
37     }
38     return 0;
39 }
AC代码

 

发表评论

0/200
245 点赞
0 评论
收藏