HDU1403(两个串的最长公共子串)

论文

题目

题意: 给你两个字符串&＃xff0c;求他们的最长公共子串。
题解&＃xff1a;将两个字符串连接成一个字符串&＃xff0c;后缀数组 get_h()&＃xff0c;h[i]代表后缀排名为i与排名为i-1的最长公共前缀。从坐标x开始的后缀与从坐标y开始的后缀的最长公共前缀最长应该是y的后缀排名和x后缀紧挨着的时候 最大。就可以用 h[]解决。
但是要满足一个条件就是x y应该在不同的串上。

emmm废话好多。 注意c[]大小应该是N.
必须在两个串之间添加一个两个串都不会出现的字符。否则影响答案正确性。

//c[]凭什么开小呜呜呜m是可以变大的啊
#include
#include
#include
using namespace std;
const int N&＃61;2e5&＃43;5;
char s[N];
int x[N],y[N],c[N],sa[N],rk[N],h[N],n,m;
void get_sa()
{for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i) c[i]&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) &＃43;&＃43;c[x[i]&＃61;s[i]];for(int i&＃61;2;i<&＃61;m;&＃43;&＃43;i) c[i]&＃43;&＃61;c[i-1];for(int i&＃61;n;i>&＃61;1;--i) sa[c[x[i]]--]&＃61;i;for(int k&＃61;1;k<&＃61;n;k<<&＃61;1){int num&＃61;0;for(int i&＃61;n-k&＃43;1;i<&＃61;n;&＃43;&＃43;i) y[&＃43;&＃43;num]&＃61;i;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) if(sa[i]>k) y[&＃43;&＃43;num]&＃61;sa[i]-k;for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i) c[i]&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) &＃43;&＃43;c[x[i]];for(int i&＃61;2;i<&＃61;m;&＃43;&＃43;i) c[i]&＃43;&＃61;c[i-1];for(int i&＃61;n;i>&＃61;1;--i) sa[c[x[y[i]]]--]&＃61;y[i];swap(x,y);x[sa[1]]&＃61;1,num&＃61;1;for(int i&＃61;2;i<&＃61;n;&＃43;&＃43;i)x[sa[i]]&＃61;(y[sa[i]]&＃61;&＃61;y[sa[i-1]]&&y[sa[i]&＃43;k]&＃61;&＃61;y[sa[i-1]&＃43;k])?num:&＃43;&＃43;num;if(num&＃61;&＃61;n) break;m&＃61;num;}
}
void get_h()
{int k&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) rk[sa[i]]&＃61;i;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){if(rk[i]&＃61;&＃61;1) continue;if(k) --k;int j&＃61;sa[rk[i]-1];while(i&＃43;k<&＃61;n&&j&＃43;k<&＃61;n&&s[i&＃43;k]&＃61;&＃61;s[j&＃43;k]) &＃43;&＃43;k;h[rk[i]]&＃61;k;}
}
int main()
{while(~scanf("%s",s&＃43;1)){int len&＃61;strlen(s&＃43;1);s[&＃43;&＃43;len]&＃61;&＃39;#&＃39;;scanf("%s",s&＃43;len&＃43;1);n&＃61;strlen(s&＃43;1),m&＃61;122;get_sa();get_h();int ans&＃61;0;for(int i&＃61;2;i<&＃61;n;&＃43;&＃43;i)if(h[i]>ans&&((sa[i]<len&&sa[i-1]>len)||(sa[i]>len&&sa[i-1]<len)))ans&＃61;h[i];printf("%d\n",ans);}
}