SSTORY - Editorial

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 https://www.codechef.com/viewsolution/14290941.

Problems like these are the reason I love Codechef long contest. Educative problem backed by a superb editorial.

5 Likes

I agree with you. The setter want me to emphasize the Suffix Automaton. So I omit the Suffix Array solution.

2 Likes

Those 2 pages of wrong answers taught me a lot of new things :slight_smile: by the HARD way… Grats to bruno!

2 Likes

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 :slight_smile:

Check your solution for this test case s1=“aecd” and s2=“acad” … the answer should be a but your solution gives c…

1 Like

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.

3 Likes

One can create many testcases based on above cases…

Hi! You can see tester’s solution :smiley:

1 Like

@rishul_nsit can you please explain this with help of one example.

thankx in advance

This algorithm itself won’t work. We need to separate the 2 strings with a special character.

http://lpcs.math.msu.su/~pritykin/csr2008presentations/starikovskaya.pdf

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: https://www.codechef.com/viewsolution/33408722
Can anyone provide me a testcase where I am failing?? @white_king @shangjingbo