串的应用kmp算法。求一个字符串在另一个字符串中第一次出现的位置。_百...
发布网友
发布时间:2022-04-23 04:58
我来回答
共2个回答
热心网友
时间:2022-04-19 01:37
KMP.java
源代码为:
package algorithm.kmp;
/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理,从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置,而不是回退到子串的第一个字符,即可提高查找的效率
* 因此为了找到这个合适的位置,先对子串预处理,从而得到一个回退位置的数组
* @param B,待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次,就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时,即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行(限于第一次执行的条件下)
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2,由此可以看出,只有当子串中含有重复字符时,回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j,把其放入P[i]中
P[i]=j;
}
return P;
}
/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时,即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行(限于第一次执行的条件下)
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果,并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}
public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配,崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}
热心网友
时间:2022-04-19 02:55
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
int lens,lent;
int next[maxn];
char S[maxn],T[maxn];
void get_next(){
int first=-1,last=0;
next[last]=first;
while(last<lent){
if(first==-1 || T[first]==T[last]){
first++,last++;
if(T[last]==T[first]) next[last]=next[first];
else next[last]=first;
}
else
first=next[first];
}
/* for(int i=0;i<=lent;i++)
printf("%d ",next[i]);
putchar('\n');*/
}
void KMP(){
int first=0,last=0;
bool find=false;
while(last<lens){
if(first==-1 || S[last]==T[first]){
last++,first++;
if(first==lent){
printf("%d\n",last-lent+1);find=true;
break;
}
}
else
first=next[first];
}
if(!find)
printf("Not Found!");
}
int main(){
freopen("x.in","r",stdin);
freopen("x.out","w",stdout);
scanf("%s%s",S,T);
lens=strlen(S);
lent=strlen(T);
get_next();
KMP();
return 0;
}
唔,打了一个c++的,如果一定要改c语言的话...也是可以的.[那就麻烦您了...2333]
测试用的样例:
x.in:
IAmVeryHappyToBeAnIndianIAmVeryHappyToBeAMiFans
ery
x.out:
5
x.in:
BaiZhiHelpsManyPeople
Zhi
x.out:
6
x.in:
TheGodIsWithYou
evil
x.out:
Not Found!
统计一个子字符串在另一个字符串中出现的次数及位置(位置存储在数组中...
void kmp(x,m,y,n,s,c)char *x;int m;char *y;int n;int* s;int* c;{ int f[50];//失败函数 int i = 0, j = 1;f[0] = -1;for (j=1;j<n;j++){ i = f[j-1];while (*(y+j) != *(y+i+1) && i>=0)i = f[i];if (*(y+j)==*(y+i+1))...
kmp算法详细算法
KMP算法通常用于在主串中查找特定模式串的出现位置。首先,我们设定两个字符串:主串s('s⑴ s⑵ s⑶ ……s(n)')和模式串p('p⑴ p⑵ p⑶…..p(m)')。当主串和模式串的第i个字符(i≤m)不匹配时,我们考察模式串的前缀子串是否与主串的某个子串相匹配。假设s(i) ≠ p(j),...
KMP算法详解
给定字符串S和模式串P,P在S中多次出现。任务是找出所有P在S中的起始下标(从0开始计数)。输入格式:- 第一行输入整数N,表示P的长度。- 第二行输入字符串P。- 第三行输入整数M,表示S的长度。- 第四行输入字符串S。输出格式:- 输出所有出现位置的起始下标,整数之间以空格分隔。数据范围:-...
c语言中如何在一个字符串中查找/出现的位置?需要第一次出现和第二次出 ...
可以使用strstr()函数查找特定字符串在目标字符串中第一次出现的位置,然后用memcpy()函数截取字符串,再使用strstr()函数查找出现位置,两次结果指针之间的字符串就是特定字符之间的字符串,希望能帮到你~
统计长度为m的字符串 在另一个字符串中出现的次数 求一个c语言程序 希 ...
这道题可以采用最笨的方法,即从第一个字符挨个比较但是这里采用KMP算法统计一个字符串在另一个字符串出现的次数,在时间和空间上开销更小*/#include<stdio.h>#include<string.h>#include<stdlib.h>int counter=0; //定义计数器,统计一个字符串在另一个字符串中出现的频率void getnext(char* ...
KMP算法详解
实现 KMP 算法关键步骤:1. 扫描原串并构建 next 数组。2. 查找 next 点:根据 next 数组的值确定跳转目标位置。3. 构建 next 数组:采用归纳法,递归查找最长可匹配前后缀。代码实现:整个匹配过程复杂度为 O(m + n)。总结:KMP 算法在字符串匹配问题上提供了一种高效解法,通过利用已经匹配的...
KMP算法详解
KMP算法是一类用于快速解决字符串匹配问题的算法,适用于查找长串(设为A)中包含的短串(设为B)的实例。相较于简单的暴力匹配法,KMP算法能显著提升效率,尤其在处理大数据集时。暴力匹配法通过遍历长串A,以当前位为起点逐个与短串B进行匹配。然而,这种方法在处理大数据时效率低下,因为它会重复比较...
KMP算法讲解
这个过程可以通过KMP算法来实现。首先,我们要明确一点,这里的字符串索引从1开始,所以当我们说到"匹配"时,不包括字符串自身的第一个字符,它的匹配数默认为0。KMP算法的核心在于构建一个部分匹配表,也称为失配函数或前缀表。这个表的目的是记录在前缀子串中,一个前缀的最长前后公共部分的长度。例如...
数据结构【串及其应用】试写一统计某文本中某些字符串的出现次数...
int i=0; //记录次数初始值,逐字符的扫描这个文本,如果有这个字符,就i++。如果没有就继续扫描下一个字符。include<stdio.h> int main(){ char cmp[3]="aba";char a[256];scanf("%s",a);int i;int count=0;for(i=0;a[i]!bai='\0';i++){ if(a[i]==cmp[0]){ int j=...
第四章——串
字符在主串中的位置:字符在串中的序号。 Eg:’1’在T中的位置是8(第一次出现)子串在主串中的位置:子串的第一个字符在主串中的位置 。 Eg:’11 Pro’在 T 中的位置为8 串是一种特殊的线性表,数据元素之间呈线性关系。串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点...