Oulipo (KMP 统计出现次数,裸题)

红太狼 2023-06-01 06:11 8阅读 0赞

目录

*  Oulipo (KMP 统计出现次数)
    
     *  题目
     *  题解及思路

# Oulipo (KMP 统计出现次数) #

## 题目 ##

求模式串在待匹配串中的出现次数。  
**Input**  
第一行是一个数字T，表明测试数据组数。之后每组数据都有两行：  
第一行为模式串，长度不大于10,000；  
第二行为待匹配串，长度不大于1,000,000。（所有字符串只由大写字母组成）  
**Output**  
每组数据输出一行结果。  
**Sample Input**  
4  
ABCD  
ABCD  
SOS  
SOSOSOS  
CDCDCDC  
CDC  
KMP  
SOEASY  
**Sample Output**  
1  
3  
0  
0

## 题解及思路 ##

就是直接KMP然后求出现次数。

**注意的地方：**

1.  next 数组的范围，也就是循环结束的地方。
2.  可能会模式串是一位的情况。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char str[1000005]; char pi[10005]; int nex[10005]; int m, n; void getNext(char *p, int *ne) { ne[0] = -1; int i = -1, j = 0; while (j < n) //注意循环的范围，之前错在 j<n-1 { if (i == -1 || p[i] == p[j]) { if (p[i + 1] == p[j + 1]) ne[++j] = ne[++i]; else ne[++j] = ++i; } else i = ne[i]; } } int kmpSearch() { int j = 0, k = 0, res = 0; //j p; while (k < m && j < n) { if (j == -1 || str[k] == pi[j]) k++, j++; else j = nex[j]; if (j == n) { res++; j = nex[j];//这里也应当注意。当模式串只有一位且等于 //主串某位的时候会死循环不加这行会 } } return res; } int main() { int T; cin >> T; while (T--) { scanf("%s", pi); scanf("%s", str); n = strlen(pi); m = strlen(str); getNext(pi, nex); cout << kmpSearch() << endl; } }

转载于:https://www.cnblogs.com/tttfu/p/11295468.html

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3461 Oulipo（KMP模板题）

Oulipo <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

阳光穿透心脏的1/2处/ 2024年02月18日 14:45/ 0 赞/ 23 阅读

相关编程题：统计数字出现次数

文章目录问题描述：解题思路：解题代码：问题描述：问题：输入任意数量的数字,统计每个数字出现的次数,并从大到小排序

蔚落/ 2023年07月14日 13:57/ 0 赞/ 28 阅读

相关 Oulipo (KMP 统计出现次数,裸题)

目录 Oulipo (KMP 统计出现次数) 题目题解及思路 Oulipo (KMP 统计出现次数) 题目求模式

红太狼/ 2023年06月01日 06:11/ 0 赞/ 9 阅读

相关 hdoj 1686 Oulipo【kmp】

Oulipo Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

水深无声/ 2022年08月04日 12:37/ 0 赞/ 146 阅读

相关 POJ - 3461 Oulipo(KMP)

[点我看题][Link 1] //这两天看了下KMP，能够去理解要怎么跳，但总感觉还缺点什么东西，只能通过刷一些题目来找找感觉题意：给一个串P，问在串T中出现了几次。

迈不过友情╰/ 2022年06月05日 08:47/ 0 赞/ 176 阅读

相关 Hdu 1686 Oulipo(KMP入门)

[传送门][Link 1] 题意：给你一个长度为W的模式串(1 ≤ |W| ≤ 10,000)和一个长度为T的文本串(|W| ≤ |T| ≤ 1,000,000)，问你这个模

墨蓝/ 2022年05月19日 06:56/ 0 赞/ 242 阅读

相关 HDU - 1686 Oulipo (KMP)

Oulipo Problem Description The French

太过爱你忘了你带给我的痛/ 2022年05月19日 06:48/ 0 赞/ 163 阅读

相关 KMP算法,oj2087,Oulipo

对于一些简单的查找我们可以用c库函数strstr include <stdio.h> include <string.h> typed

超、凢脫俗/ 2022年04月15日 02:46/ 0 赞/ 160 阅读

相关统计字母出现的次数

输入一个字符串，统计其中字符 A 的数量并且输出。输入格式输入共有一行，为一个不带空格的字符串（其中字符数不超过 100100）。输出格式输出一行，包含一

系统管理员/ 2022年03月16日 06:40/ 0 赞/ 368 阅读

相关统计字符出现的次数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmdo

灰太狼/ 2022年01月23日 10:51/ 0 赞/ 423 阅读