赞
踩
#include<stdio.h>
#include<string.h>
#include<iostream>
#define MAX 255
using namespace std ;
typedef struct {
int count ;
char str[MAX];
}PP ;
int BF(PP S ,PP T, int pos )
{
int i = pos; // i 指向主串
int j = 1; // j 指向模式串
while(i <= S.count && j<= T.count)
{
if( S.str[i] == T.str[j]){
i++ ;
j++ ;
}
else { //不匹配时,就让T的第一个字符与S的第二个字符进行比较
j= 1 ;
i = i-j + 2 ;
}
}
if(j > T.count) // j大于长度时,就是成功匹配,返回第一个字符在主串中的下标,即i-T.count
return i-T.count;
else
return 0;
}
int main(void)
{
PP S,T ;
S.str[0]=' ';
T.str[0]=' ';
cout << "请输入主串:" << endl ;
scanf("%s",&S.str[1]);
cout << "请输入模式匹配串:" << endl ;
scanf("%s",&T.str[1]);
S.count = strlen(S.str)-1;
T.count = strlen(T.str)-1;
printf("S.str==%s\n",S.str) ;
printf("S.count ==%d\n",S.count);
printf("T.str==%s\n",T.str);
printf("T.count ==%d\n",T.count);
int pos ;
cout << "请输入模式匹配串要在主串的何处开始匹配查找 :" << endl ;
scanf("%d",&pos);
cout << BF(S,T,pos) << endl ;
}
#include<stdio.h>
#include<string.h>
#include<iostream>
#define MAX 255
using namespace std ;
typedef struct {
int count ;
char str[MAX];
}PP ;
void get_next(PP T , int *next)
{
int after , front;
after= 1; // 表示后缀
front= 0; // 表示前缀
next[1]= 0;
while(after <= T.count )
{
if( front== 0 || T.str[after] == T.str[front]){
after++;
front++;
next[after] = front;
}
else {
//front 回溯,关键点
front=next[front];
}
}
}
// 返回字串T 在主串S中的位置,不存在返回 0
int index_kmp(PP S ,PP T, int pos )
{
int i = pos;
int j = 1;
int next[MAX] ;
get_next(T,next);
while(i <= S.count && j<= T.count)
{
if( j == 0 || S.str[i] == T.str[j]){
i++ ;
j++ ;
}
else {
j=next[j]; //改变 j 就是在移动 T 模式串
}
}
if(j > T.count)
return i-T.count;
else
return 0;
}
//前缀是固定的,二后缀是相对的
int main(void)
{
PP S,T ;
S.str[0]=' ';
T.str[0]=' ';
cout << "请输入主串:" << endl ;
scanf("%s",&S.str[1]);
cout << "请输入模式匹配串:" << endl ;
scanf("%s",&T.str[1]);
S.count = strlen(S.str)-1;
T.count = strlen(T.str)-1;
printf("S.str==%s\n",S.str) ;
printf("S.count ==%d\n",S.count);
printf("T.str==%s\n",T.str);
printf("T.count ==%d\n",T.count);
int pos ;
cout << "请输入模式匹配串要在主串的何处开始匹配查找 :" << endl ;
scanf("%d",&pos);
cout << index_kmp(S,T,pos) << endl ;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。