Another solution using Suffix Array can be found here : http://www.roman10.net/2012/03/16/suffix-array-part-3-longest-common-substring-lcs/
How to find LCS given Suffix Automaton? If the first character of the pattern doesn’t exist in the text, how would the state change?
Btw, my solution with Suffix Arrays gets TLE CodeChef: Practical coding for everyone.
Problems like these are the reason I love Codechef long contest. Educative problem backed by a superb editorial.
I agree with you. The setter want me to emphasize the Suffix Automaton. So I omit the Suffix Array solution.
Those 2 pages of wrong answers taught me a lot of new things by the HARD way… Grats to bruno!
Try going trough this link, maybe it will help you out:
http://discuss.codechef.com/questions/39834/wa-in-sstory-suffix-arrays
@kuruma Thanks but my code works on all the test cases mentioned there. Can you provide some tricky case?
Try to look at my code along with explanation
Check your solution for this test case s1=“aecd” and s2=“acad” … the answer should be a but your solution gives c…
We can still have the other approach mentioned. The Editorial should be as elaborate as possible and may capture multiple ways of solving the problem. It is also made a community wiki so that anyone can edit/add to it.
One can create many testcases based on above cases…
Hi! You can see tester’s solution
This algorithm itself won’t work. We need to separate the 2 strings with a special character.
This testdata will hack you stand-code.
answer is:
ddrqq
5
You can proved all of the two string have same sub-string"ddrqq"。so the resulted corret answer can’t be accepted.
datklbenxbvnhohoueazpadvpszrogluiewtogshnelpszrxwsubicupvftjeszoyfbhswmabhushwlmvmnbicgziqcjtastrwaklcocehbzsjukdvjeqoqoybrhtnhtnvjxzfrpafmweznvpqcqlbdknvpqsavghvxareontsiahscdflaoriniivwdfoiyqtxutbhpgyuntgbujmgmiaaifezatcjdpjterfrjrymzaopceutldqleonyjmefbvlokudddrqqspnfmnjrxkqbksmiaitcqhlrkwqctqgpyvemmnirwzxzurrkhzlllyneiiravkbgpcmwttbwthzwmfhuaetbgdiwsfvtdmuynyzknggqklpumniutelshrlcredsvidpphzubnqwwttdozbthhrqgwiahzzusyexnkyndhamsvekjezzkxxgzawsqmummxewmnlgirgdudjonutcwegvkxrjktaomchknkkdyhmuzvedhfqebzguzqfszdqynkmhicrzwtdbmoloayuwzciurykihtwgtsafpommkndzahpyczewifffcdkyyormyvsmrccxjqxvagwjfpsxafjbdbccoymsfyxebmdxxfehgpjcssfirjuvdyiyhgjbnwubllcklndctjnmvkjygvfeubrbcmtwskwtaltnorrfdqvdvcjjnzlgcfeyzmeqhodcyqndvgjscgwmquilsdccbhdlvjpraicvbajarpwhwcxtdkfyxfomxccnbhqojogbdgmvcryrrqxdsbzwyrixxdtrsmypijwmynphdtohlopvhystnlguxvsvlyqlrwfqwjrsqjzoqdtbokrbsjfpljmyqctrijizpmfpxpyecreshjdeepevhkufovohjmgqwyrwkumzpfbivrlixvuzpkyyvbxizjubfgoutyubgzhgoyiqmsmwbvrbyobsultcqcvgaxhnjnxhjuxhfvaqvhbpfciop
etghkjwberdsowmryzchanfdtcltwdljchkmjppodllfehzojvxgjnkbcwqsxyvuumazeorzlznooqosuqyhxsuwurdxamjcbprixbvhcjyqcssnuekuyzfmfggiysegbdgfexgewioictohziwwqlqcbpjkseobsopmybaogblwlshrtrnpmbozlunvrvansbqutlktgufbrhznywpsouhfiljggjpzceivzidzwbbbewpdbgkvwssadxhxspbrdqwpkvdchxwqzvwhdyeipletdhkmjpmpetfkfjfyahvwkbkpqrljrydorkjthobpmgqultyawdwtpsrbstpqlxcsadyihbnxrybrmfessaxrbkifqpnqtjervkgsjjthnauyuqwmhjnyonmbepombvliztigvvtrujebriciknrfhywjktrcssnjszqwufwkohmvcsrimrxqagebykefuzdyauqnmgtgcbsjweqsqzynbcegjjkxtgwjrzdhekkonlxbfvtwuhrijdkaemsgecfdmroeszgtswkhtovyoikpenmvdxcycpasuvumumfjjonbwoghuiekwoiryrypiovnpagdbiummhrjsmxpduyfwhsyxihxzdytliucfcywgjfmeannsjstdcszvrelcluaeiynirlfhlnpzficminzhkwhfaztsvbmlofphdzqxxsifdtcoukrccjqwznagffzremfkqlzftvwssrhdcrccrathqddrqqzdrhbbvuadoyzljokqncenuaqfhxwhmnyyanzjixfwudvenrqqvkdssnztfargogopmtppuloqkhehsvlczinmwdaidngschynunjdqinbhbatiyaoyhxbajlrswbgpkaxkugrhgawwaeomerktirlpukkegbhseekilvdiutzuoeuawwzdxqzehotgcghkiqnfuutpjgfpnjytvfrxmopqnxvhwnmclihxuqxrgwkalczxck
this is my code,can’t be accepted
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
char s[N],t[N];
int x,y,n,a[N],cntA[N],cntB[N],sa[N],rk[N],tsa[N],A[N],B[N],h[N],dp[N][25];
void de()
{
cout<<“OK”<<endl;
}
void solve()
{
memset(cntA,0,sizeof(cntA));
for(int i=1;i<=n;i++) cntA[a[i]]++;
for(int i=1;i<=100;i++) cntA[i]+=cntA[i-1];
for(int i=n;i>=1;i–) sa[cntA[a[i]]–]=i;
rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
rk[sa[i]]=rk[sa[i-1]];
if(a[sa[i]]!=a[sa[i-1]]) rk[sa[i]]++;
}
for(int l=1;rk[sa[n]]<n;l<<=1)
{
for(int i=0;i<=n;i++) cntA[i]=cntB[i]=0;
for(int i=1;i<=n;i++)
{
cntA[A[i]=rk[i]]++;
cntB[B[i]=i+l<=n?rk[i+l]:0]++;
}
for(int i=1;i<=n;i++)
cntB[i]+=cntB[i-1],cntA[i]+=cntA[i-1];
for(int i=n;i>=1;i–) tsa[cntB[B[i]]–]=i;
for(int i=n;i>=1;i–) sa[cntA[A[tsa[i]]]–]=tsa[i];
rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
rk[sa[i]]=rk[sa[i-1]];
if(A[sa[i]]!=A[sa[i-1]]||B[sa[i]]!=B[sa[i-1]]) rk[sa[i]]++;
}
}
for(int i=1,j=0;i<=n;i++)
{
if(j)j–;
while(a[i+j]==a[sa[rk[i]-1]+j]) j++;
h[rk[i]]=j;
}
}
void st()
{
for(int i=1;i<=n;i++)
dp[i][0]=h[i];
for(int i=1;1<<i<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int k=log2(r-l+1);
return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
void rrr()
{
srand(time(0));
int n=1000,m=1000;
for(int i=1;i<=n;i++)
putchar(rand()%26+‘a’);putchar(’\n’);
for(int i=1;i<=m;i++)
putchar(rand()%26+‘a’);putchar(’\n’);
}
int main()
{
//rrr();
scanf("%s",s+1);
scanf("%s",t+1);
x=strlen(s+1);y=strlen(t+1);n=x+y;
/*
string ss=“ddrqq”;
for(int i=1;i+4<=x;i++)
{
bool flag=true;
for(int j=i;j<=i+4;j++)
if(s[j]!=ss[j-i]) flag=false;
if(flag) cout<<“RNGNB”<<endl;
}
for(int i=1;i+4<=y;i++)
{
bool flag=true;
for(int j=i;j<=i+4;j++)
if(t[j]!=ss[j-i]) flag=false;
if(flag) cout<<“RNGNB”<<endl;
}
/
for(int i=1;i<=y;i++)
s[x+i]=t[i];
s[n+1]=’\n’;
for(int i=1;i<=n;i++)
a[i]=s[i]-‘a’+1;
solve();
st();
int pre=0,mx=0,ans=0;
for(int i=1;i<=n;i++)
{
if(sa[i]<=x) pre=i;
else
{
if(pre)
{
int s=min(query(pre+1,i),n-sa[i]+1);
if(s>mx) mx=s,ans=sa[i];
else if(s==mx) ans=min(ans,sa[i]);
}
}
}
pre=0;
for(int i=1;i<=n;i++)
{
if(sa[i]>x) pre=i;
else
{
if(pre)
{
int s=min(query(pre+1,i),n-sa[pre]+1);
if(s>mx) mx=s,ans=sa[pre];
else if(s==mx) ans=min(ans,sa[pre]);
}
}
}
if(mx)
{
for(int i=ans;i<=ans+mx-1;i++)
putchar(s[i]);
putchar(’\n’);
}
printf("%d\n",mx);
}
/
rjrymzaopceutldqleonyjmefbvlokudddrqqspnfmnjrxkqbksmiaitcqhlrkwqctqgpyvemmnirwzxzurrkhzlllyneiiravkbgpcmwttbwthzwmfhuaetbgdiwsfvtdmuyn
xsifdtcoukrccjqwznagffzremfkqlzftvwssrhdcrccrathqddrqqzdrhbbvuadoyzljokqncenuaqfhxwhmnyyanzjixfwudvenrqqvkdssnztfargogopmtpp
datklbenxbvnhohoueazpadvpszrogluiewtogshnelpszrxwsubicupvftjeszoyfbhswmabhushwlmvmnbicgziqcjtastrwaklcocehbzsjukdvjeqoqoybrhtnhtnvjxzfrpafmweznvpqcqlbdknvpqsavghvxareontsiahscdflaoriniivwdfoiyqtxutbhpgyuntgbujmgmiaaifezatcjdpjterfrjrymzaopceutldqleonyjmefbvlokudddrqqspnfmnjrxkqbksmiaitcqhlrkwqctqgpyvemmnirwzxzurrkhzlllyneiiravkbgpcmwttbwthzwmfhuaetbgdiwsfvtdmuynyzknggqklpumniutelshrlcredsvidpphzubnqwwttdozbthhrqgwiahzzusyexnkyndhamsvekjezzkxxgzawsqmummxewmnlgirgdudjonutcwegvkxrjktaomchknkkdyhmuzvedhfqebzguzqfszdqynkmhicrzwtdbmoloayuwzciurykihtwgtsafpommkndzahpyczewifffcdkyyormyvsmrccxjqxvagwjfpsxafjbdbccoymsfyxebmdxxfehgpjcssfirjuvdyiyhgjbnwubllcklndctjnmvkjygvfeubrbcmtwskwtaltnorrfdqvdvcjjnzlgcfeyzmeqhodcyqndvgjscgwmquilsdccbhdlvjpraicvbajarpwhwcxtdkfyxfomxccnbhqojogbdgmvcryrrqxdsbzwyrixxdtrsmypijwmynphdtohlopvhystnlguxvsvlyqlrwfqwjrsqjzoqdtbokrbsjfpljmyqctrijizpmfpxpyecreshjdeepevhkufovohjmgqwyrwkumzpfbivrlixvuzpkyyvbxizjubfgoutyubgzhgoyiqmsmwbvrbyobsultcqcvgaxhnjnxhjuxhfvaqvhbpfciop
etghkjwberdsowmryzchanfdtcltwdljchkmjppodllfehzojvxgjnkbcwqsxyvuumazeorzlznooqosuqyhxsuwurdxamjcbprixbvhcjyqcssnuekuyzfmfggiysegbdgfexgewioictohziwwqlqcbpjkseobsopmybaogblwlshrtrnpmbozlunvrvansbqutlktgufbrhznywpsouhfiljggjpzceivzidzwbbbewpdbgkvwssadxhxspbrdqwpkvdchxwqzvwhdyeipletdhkmjpmpetfkfjfyahvwkbkpqrljrydorkjthobpmgqultyawdwtpsrbstpqlxcsadyihbnxrybrmfessaxrbkifqpnqtjervkgsjjthnauyuqwmhjnyonmbepombvliztigvvtrujebriciknrfhywjktrcssnjszqwufwkohmvcsrimrxqagebykefuzdyauqnmgtgcbsjweqsqzynbcegjjkxtgwjrzdhekkonlxbfvtwuhrijdkaemsgecfdmroeszgtswkhtovyoikpenmvdxcycpasuvumumfjjonbwoghuiekwoiryrypiovnpagdbiummhrjsmxpduyfwhsyxihxzdytliucfcywgjfmeannsjstdcszvrelcluaeiynirlfhlnpzficminzhkwhfaztsvbmlofphdzqxxsifdtcoukrccjqwznagffzremfkqlzftvwssrhdcrccrathqddrqqzdrhbbvuadoyzljokqncenuaqfhxwhmnyyanzjixfwudvenrqqvkdssnztfargogopmtppuloqkhehsvlczinmwdaidngschynunjdqinbhbatiyaoyhxbajlrswbgpkaxkugrhgawwaeomerktirlpukkegbhseekilvdiutzuoeuawwzdxqzehotgcghkiqnfuutpjgfpnjytvfrxmopqnxvhwnmclihxuqxrgwkalczxck
*/
I tried using BS + Hashing. Here is my solution: CodeChef: Practical coding for everyone
Can anyone provide me a testcase where I am failing?? @white_king @shangjingbo