Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 大佬们帮忙看看re是怎么回事。。。

Posted by Dale123 at 2018-05-18 20:40:15 on Problem 2774
```#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define sqr(a) (a)*(a)
#define For(i,m,n) for(int i=m;i<=n;i++)
#define Dor(i,n,m) for(int i=n;i>=m;i--)
#define lan(a,b) memset(a,b,sizeof(a))
#define maxn 200010

using namespace std;

char s[maxn];
char s1[maxn],s2[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n,m;///n是字符串长度,m为模板长度
int _rank[maxn],height[maxn];

void build_sa(int m)
{
int *x=t,*y=t2;
///基数排序
For(i,0,m-1)c[i]=0;
For(i,0,n-1)c[x[i]=s[i]-'a']++;
For(i,1,m-1)c[i]+=c[i-1];
Dor(i,n-1,0)sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
///直接利用sa数组排序第二关键字
for(int i=n-k;i<n;i++)y[p++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
///基数排序第一关键字
For(i,0,m-1)c[i]=0;
For(i,0,n-1)c[x[y[i]]]++;
For(i,0,m-1)c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
///根据sa和y数组计算新的x数组
swap(x,y);
p=1;x[sa[0]]=0;
for(int i=1;i<n;i++)
x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n)///以后即使继续倍增，sa也不会改变，退出
break;
m=p;///下次基数排序的最大值

}
}

int cmp_suffix(char* pattern,int p)
{
return strncmp(pattern,s+sa[p],m);
}

void getheight()
{
int k=0;
For(i,0,n-1) _rank[sa[i]]=i;
For(i,0,n-1)
{
if(k) k--;
int j=sa[_rank[i]-1];
while(s[i+k]==s[j+k]) k++;
height[_rank[i]]=k;
}
}

int main()
{
int p,q;
while(~scanf("%s",s1))
{
scanf("%s",s2);
p=strlen(s1);
q=strlen(s2);
n=0;
for(int i=0;i<p;i++)
s[n++]=s1[i];
s[n++]='z'+1;
for(int i=0;i<q;i++)
s[n++]=s2[i];
s[n]='\0';
//printf("%s\n",s);
build_sa(30);
getheight();
int ans=0;
for(int i=1;i<n;i++)
{
//printf("height %d=%d\n",i,height[i]);
if(height[i]>ans)
{
if((sa[i-1]<p&&sa[i]>p)||(sa[i-1]>p&&sa[i]<p))
ans=height[i];
}
}
printf("%d\n",ans);
}
return 0;
}
```

Followed by: