POJ 3415 Common Substrings
單調棧的思想很巧妙，若進入的元素比棧頂小，則棧頂出棧，把相應信息更新一下，直到要進入的元素比棧頂元素大
//注意這道題和Facer’s string這道題的區別
//該題求的是sa[i]-sa[j]的lcp，需要用到的是height[i+1]-height[j]
//而 Facer’s string這道題用到的是height[i]-height[j]的值，涉及到的是sa[i-1]-sa[j]
#include
#include
#include
using namespace std;
typedef long long ll;
#define N 100005
char s[N];
int r[N],sa[N],height[N],rank[N],wa[N],wb[N],wv[N],ws[N];
int cmp(int *r,int a,int b,int l){
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m){
int i,j,p,*x=wa,*y=wb;
for(i=0;i=0;i--) sa[--ws[x[i]]]=i;
for(j=1,p=1;p=j) y[p++]=sa[i]-j;
for(i=0;i=0;i--) sa[--ws[wv[i]]]=y[i];
swap(x,y);
for(p=1,x[sa[0]]=0,i=1;ibot&&height[i]<=sta[top-1][0]) {
t-=(sta[top-1][0]-height[i])*sta[top-1][1];//減去差值
weight+=sta[top-1][1];
top--;
}
sta[top][0]=height[i];
sta[top++][1]=weight;
if(sa[i]>n1) ans+=t;//如果當前串是B串（注意是sa[i],不是sa[i-1]），則加上前面的總和
}
}
t=0,bot=0,top=0;
for(int i=1;i<=l;i++){
if(height[i]n1) weight++,t+=height[i]-k+1;
while(top>bot&&height[i]<=sta[top-1][0]) {
t-=(sta[top-1][0]-height[i])*sta[top-1][1];
weight+=sta[top-1][1];
top--;
}
sta[top][0]=height[i];
sta[top++][1]=weight;
if(sa[i]
