4.cpp

这是bf求最长公共子列

#include<stdlib.h>
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define N 10
int M;

//int IndexBF ( char S [ ], char T [ ], int pos ) 
void IndexBF ( char S [ ], char T [ ], int pos )
{ 

/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1    */
int i = pos, j = 0; 
while (S[i+j] != '\0'&& T[j] != '\0') 
if ( S[i+j] == T[j] ) 
j ++; // 继续比较后一字符
else 
{ 
i ++; j = 0; // 重新开始新的一轮匹配 
} 
if ( T[j] == '\0')
M=i; // 匹配成功   返回下标 

else
M=-1;  // 串S中(第pos个字符起)不存在和串T相同的子串

} // IndexBF


void main()
{
	char S[N],a[N];
	int n,m2,m1,k;
	m1=m2=0;
	cout<<"please input T:"<<endl;
	cin>>n;
	cout<<"please input the string S:"<<endl;
    gets(S);
	k=strlen(S);
	if(k<n)
	{
		cout<<"the T is smaller than the length of the string"<<endl;
		return;
	}
	else
	{
		M=0;
		int start=0;
		for(int i=n;i<k;i++)
/**/ 			for(int q=0;q<k-n;q++)
			for(int j=q;j<q+n;j++)
		//	{
     
//		for(int j=0;j<n;j++)
			a[j]=S[j];
		    a[n]='\0';
		
			
			while(M!=-1)
			{
				IndexBF(S,a,start);
				start=M+n;
				m1++;
				//cout<<"@";
			}
			m1--;
		if(m1>m2) m2=m1;
			m1=0;		
	// }	
	}
	   cout<<m2<<endl;   
}