7-1 jmu-ds-实现KMP 分数 10
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int MAX_LEN = 20010;
//本题运用到字符串比对中的next[j]求法具体算法可以直接百度
//get_next就是用于求next[j]的这里只需要传入目标串就行
void get_next(char str[] ,int len, int next[])
{
int i=0,j=0;
next[0]= -1;
for(i=0;i<len;i++)
{
while(j>0 && str[i] !=str[j])
{
j=next[j-1];
if(str[i]==str[j]) j++;
next[i]=j;
}
}
}
int find(char s[] ,int len_s ,char t[],int len_t,int next[])
{
int i=0;
int j=0;
while(i<len_s&&j<len_t)
{
if(j ==-1||s[i]==t[j])
{
j++;
i++;
}
else
{
j=next[j];
}
}
if(j==len_t)
return i-j;
else
return -1;
}
int main ()
{
int cas;
char s[MAX_LEN],t[MAX_LEN];
int next[MAX_LEN];
scanf("%d" ,&cas);
while(cas--)
{
scanf("%s %s",s,t);
int len_s=strlen(s);//求出字符串的长度
int len_t=strlen(t);
get_next(t,len_t,next);//针对目标字符串求出next【j】
if(find(s,len_s,t,len_t,next)!=-1)
{ printf("%d\n",find(s,len_s,t,len_t,next));
}
else{
printf("not find!\n");}
}
}
给两个字符串A、B, 从A中找出第一次出现B的位置。
输入格式:
第一行输入一个整数n，表示测试数据的个数
对于每组测试数据，输入两个字符串S T，S和T中间用一个空格隔开，每组数据占一行。
输出格式:
对于每组测试数据，输出A中找出第一次出现B的位置，如果A不包含B，输出“not find!”
输入样例:
3
abcdabbcd abbc
abcd efg
abbcdd bbc
上面是代码下面是有关模式传中next[j]以及nextval[j]的求法输出样例:
4
not find!
1
