8592 KMP算法

8592 KMP算法

时间限制:1000MS  内存限制:1000K

题型: 编程题   语言: 无限制
描写叙述

用KMP算法对主串和模式串进行模式匹配。

本题目给出部分代码。请补全内容。

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define INFEASLBLE  -1
#define OVERFLOW  -2
#define MAXSTRLEN  255     //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];    //0号单元存放串的长度
 
void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
   // 请补全代码
 
 
 
 
}
 
int Index_KMP(SString S,SString T,int pos){
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。

请补全代码 } void main() { SString T,S; int i,j,n; char ch; int pos; scanf(“%d”,&n); // 指定n对需进行模式匹配的字符串 ch=getchar(); for(j=1;j<=n;j++) { ch=getchar(); for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入主串 { S[i]=ch; ch=getchar(); } S[0]=i-1; // S[0]用于存储主串中字符个数 ch=getchar(); for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入模式串 { T[i]=ch; ch=getchar(); } T[0]=i-1; // T[0]用于存储模式串中字符个数 pos= ; // 请填空 printf("%d\n",pos); } }

输入格式

第一行：输入n，表示有n对字符串须要匹配
第二行：输入第1个主串
第三行：输入第1个模式串
第四行：输入第2个主串
第五行：输入第2个模式串
……
倒数二行：输入第n个主串
最后一行：输入第n个模式串

输出格式

第一至第n行：输出每对应模式串的匹配值
输入例子

4
oadhifgoarhglkdsa
oar
abcdefg
dec
algeojflas
ojf
jfaweiof
of
输出例子

8
0
5

7

实现方法例如以下：

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define INFEASLBLE  -1
#define OVERFLOW  -2
#define MAXSTRLEN  255     //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];    //0号单元存放串的长度
 
void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
   // 请补全代码
 
    int i=1,j=0;
    next[1]=0;
    while(i<T[0])
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
    else j=next[j];
    }
 
}
 
 
 
int Index_KMP(SString S,SString T,int pos)
{
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。

请补全代码 int i=pos=1,j=1; int next[256]; while(i<=S[0]&&j<=T[0]) { if(j==0||S[i]==T[j]) { ++i; ++j; } else { get_next(T,next); j=next[j ]; } } if(j>T[0]) return i-T[0]; else return 0; } int main() { SString T,S; int i,j,n; char ch; int next[256]; int pos; scanf("%d",&n); // 指定n对需进行模式匹配的字符串 ch=getchar(); for(j=1;j<=n;j++) { ch=getchar(); for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入主串 { S[i]=ch; ch=getchar(); } S[0]=i-1; // S[0]用于存储主串中字符个数 ch=getchar(); for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入模式串 { T[i]=ch; ch=getchar(); } T[0]=i-1; // T[0]用于存储模式串中字符个数 //pos=Index_KMP(S,T,1); // 请填空 pos=Index_KMP(S,T,pos); printf("%d\n",pos); } return 0; }