有问题.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include <algorithm>
using namespace std;

#define MAXLEN 100005
int n,bn; //字符串长度
int power, lstSA[MAXLEN], lstRank[MAXLEN], 
SA [MAXLEN], rank[MAXLEN], h[MAXLEN], height[MAXLEN];
 //后缀排序数组，名次数组，
 //height[i]=lcs(suffix(SA[i-1]),suffix(SA[i]))
 //h[i]=height[rank[i]]
int r[50][MAXLEN];//rmq预处理数组
char str[MAXLEN],strb[MAXLEN];//字符串

void suffixArray();//后缀排序，求出SA，Rank
void lcs();//求出height，h
void rmq();//预处理rmq
int asklcs(int x, int y);//询问后缀排名为x和y之间的lcs

//注意不要忘记先在字符串结尾加上结束符'$'

int ans;

void print()
{
	int i;
	printf("SA  rank   h   height\n");
	for(i=0;i<n;i++)
	{
		printf("%3d %3d %3d %3d\n",SA[i],rank[i],h[i],height[i]);
	}
}

void print_sa()
{
	int i;
	for(i=0;i<n;i++)
		printf("%s\n",&str[SA[i]]);
	printf("\n");
}
bool cmpLst(const int& a, const int& b)
{
  return lstRank[a]<lstRank[b]||lstRank[a]==lstRank[b]&&lstRank[a+power]<lstRank[b+power];
}

bool cmpChar(const char &a,const char &b)
{
	return str[a]<str[b];
}	

void suffixArray()
{
	int i,j;
  for (i = 0; i<n; i++) SA[i] = i;
  sort(SA, SA+n, cmpChar);
  for (i = 0, j = 0; i<n; i++) {
    if (i>0&&str[SA[i]]!=str[SA[i-1]]) j++;
    rank[SA[i]] = j;
  }
  for (power = 1; rank[SA[n-1]]<n-1; power *= 2) {
    memcpy(lstRank, rank, sizeof(int)*n);
    memcpy(lstSA, SA, sizeof(int)*n);
    sort(SA, SA+n, cmpLst);
    for (int i = 0, j = 0; i<n; i++) {
      if (i>0&&cmpLst(SA[i-1], SA[i])) j++;
      rank[SA[i]] = j;
    }
  }
}

void lcs()
{
// 这一部分写烦了，改天贴上好一点的
	int i;
  for (i = 0; i<n; i++) 
  {
    if (rank[i]==0) {h[i] = 0; continue;}
    int j = rank[i]-1, k = rank[i], s;
    if (i==0||h[i-1]<=1) s = 0;
    else s = h[i-1]-1;
for (; SA[k]+s<n&&SA[j]+s<n; s++)
 if (str[SA[k] +s]!=str[SA[j]+s]) break;
    h[i] = s;
  }
  for (i = 0; i<n; i++)
    height[rank[i]] = h[i];
}

void rmq()
{
  int i;
  for (i = 0; i<n; i++)
    r[0][i] = height[i];
  for (int k = 1; (1<<k)<=n; k++) {
    for (int i = 0; i<n; i++) {
      r[k][i] = r[k-1][i];
      if (i+(1<<(k-1))<n&&r[k-1][i+(1<<(k-1))]<r[k][i])
    r[k][i] = r[k-1][i+(1<<(k-1))];
    }
  }
}

void print_rmq()
{
	int k,i;
	 for(i=0;i<n;i++) printf("%3d",i);
	 printf("\n");
	for(k=0;(1<<k)<=n;k++)
	{
		for(i=0;i<n;i++)
			printf("%3d",r[k][i]);
		printf("\n");
	}
}

int min(int a,int b)
{
	return a<b?a:b;
}

int asklcs(int x, int y)
{
  if (x>y) swap(x, y);
  int k = 0;
  if(x==y) return n-SA[x]+1;
  while ((1<<k)<=(y-x)) k++;
  k--;
//  printf("k=%d\n",k);
  return min(r[k][x+1], r[k][y-(1<<k)+1]);
}

int getlcs(int st)
{//求b[]串st位置开始的后缀与r[]的最长公共前缀
  int left=0,right=n-1,maxmatch=0,mid,lcp,rr;
  bool flag;
  ans=mid=(left+right)/2;
  while(left<=right)
  {
 // 	if(maxmatch>0)
//	{
	lcp=asklcs(mid,ans);
	if(lcp<maxmatch)
	{
		rr=lcp;
		flag=str[SA[mid]+rr]<strb[st+rr];
	}
	else
	{
		for(rr=maxmatch;;rr++)
		{
			if(str[SA[mid]+rr]!=strb[st+rr]) 
			{
				flag=str[SA[mid]+rr]<strb[st+rr];
				break;
			}
		}
		maxmatch=rr;
		ans=mid;
		if(maxmatch==bn-st) return maxmatch;
	}
//	}
//	else
//	{
//		flag=str[SA[mid]]<strb[st+mid
//	}
	if(flag) left=mid+1;
	else right=mid-1;
	mid=(left+right)/2;
  }
  return maxmatch;
}

void init()
{
	suffixArray();
	lcs();
	rmq();
}
int main()
{
//	int ma,mb;
	int ma=0,mb,mmax=0,i,j;
	scanf("%s",&str);
	n=strlen(str);
	str[n]='$';str[n+1]='\0';
//	printf("%s\n",str);
	init();
//	print_sa();
//	print();
//	print_rmq();
	scanf("%s",&strb);
//	{
		bn=strlen(strb);
/*		for(i=0;i<bn;i++)
		{
			if(ma==0) {mb=getlcs(i);j=0;}
			if(mb>0 && str[SA[ans]+1+j]==strb[i+1]) {ma=1;++j;}
			else {ma=0;j=0;}
			if(mmax<mb) mmax=mb;
		}
*/		
		
		for(i=0;i<bn;i++)
		{
			mb=getlcs(i);
			if(mmax<mb) mmax=mb;
		}
		printf("%d\n",mmax);
//		system("pause");
//	}
//	printf("%d\n",getlcs(0));
//	while(scanf("%d %d",&ma,&mb)!=EOF)
//	{
//		printf("%d\n",asklcs(ma,mb));
//	}
	return 0;
}