学步园

55、字符串匹配实现

请以俩种方法，回溯与不回溯算法实现。

/*
55、字符串匹配实现
请以俩种方法，回溯与不回溯算法实现。

回溯法，即最基本的方法。算法复杂度O( m * n )
　　设主串mainStr = { S0, S1, S2, …, Sm },
　　模式串matchStr = { T0, T1, T2, …, Tn };
　　当T[0]…T[j-1] ==S[i-j]…S[i-1]，即模式串的前j个字符已经和主串匹配，
当前要比较T[j]和S[i]是否相等？
　　如果T[j] == S[i], 则i++, j++,继续比较下一个
　　如果T[j] != S[i], 则i要回溯，也就是i要退回到与j开始匹配时的下一个位置。
同时j=0, 表示模式串从头开始，重新匹配。

不回溯：即用KMP算法。算法复杂度O( m + n )。
　　在KMP中，如果T[j] != S[i]，则i保持不动（即，不回溯）。
同时，j不用清零，而是向右滑动模式串，用T[k]和S[i]继续匹配。
关键求一个next的数组 
*/


#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#define N 100 
using namespace std;

int search1(char* src, char* pat)  //回溯法 
{  
    int i=0,j=0;
	int slen=strlen(src),plen=strlen(pat); 
	 
    while(i<slen&&j<plen)  
    {  
        if(src[i]==pat[j])  //如果相同，则两者++，继续比较  
        {  
            ++i;++j;             
        }  
        else  
        {  
            //否则，指针回溯，重新开始匹配  
            i=i-j+1;  //退回到最开始时比较的位置  
            j=0;  
        }  
    }  
    if(j>=plen)//说明已经匹配 跳出的 
        return i-plen;   
    else  
        return -1;  
} 

int* PrefixFunc(char *query)//处理next数组 
{  
    if (query == NULL) 
        return NULL;  
    int len=strlen(query);      
    int *Pre=new int[len];  
	int k=-1,i; 
	
    Pre[0]=-1;  
    for(i=1;i<len;i++)
	{  
        while(k>-1&&query[k+1]!=query[i])  
            k=Pre[k];  
         
        if (query[k+1]==query[i]) 
            k++;  
        Pre[i]=k;  
    }  
    return Pre;  
}
  
int KMP(char *src, char *pat)  
{  
    if (src==NULL||pat==NULL)  
        return -1;  
   
    int slen=strlen(src);  
    int plen=strlen(pat);  
    int *Prefix; 
    Prefix=PrefixFunc(pat);  //next数组 
    if (Prefix==NULL) 
        return -1;  
    
    int k=-1,i;  
    for (i=0;i<slen;i++)
	{  
        while(k>-1&&pat[k+1]!=src[i])  
            k=Prefix[k];  
         
        if (pat[k+1]==src[i]){  
            k++;  
        }  
        if (k==plen-1)
		{  
            cout<<"KMP:match in position:"<<" "<<i-plen+ 1<<" "<<endl;  
            k=Prefix[i]; 
			delete[] Prefix;//只找一次  
            return 0;
        }  
          
    }  
    delete[] Prefix;  
    return 0;  
}

int main()
{
	int n,i;
	char src[N],pat[N]; 
	while(1)
	{
		scanf("%s",src);
		if(!strcmp(src,"0")) break;
		scanf("%s",pat);
			
		printf("method1:match in position:%d\n",search1(src,pat)); 
		KMP(src,pat);
	} 
	return 0;
}
/*
BBCABCDABABCDABCDABDE
ABCDABD
bacbababaabcbab
abc
*/