This is painful problem, I spent 3 hours to solve, but very educational actually. If you are struggling, than read this: https://codeforces.com/topic/60789/ru9

Using the same code, and only switching the order of the 2 input strings ...
    scanf("%s", strr);
    scanf("%s", strl);
leads to WA5

switching the order (shouldn`t make any difference)
    scanf("%s", strl);
    scanf("%s", strr);
and I get WA6

Just curious did anyone managed to pass the time limit
using binary search + rolling hash or the test data are
specially designed to be solved in time only by an efficient suffix tree/array implementation?

Does anyone see what goes wrong with my program for the input of test #9? or test inputs maybe?


EDIT: Test Case found!

Edited by author 01.06.2012 22:08

Plz help me, I used hashing with binary search and got WA on 52.

use N = 100001 instead N = 100000

I have got a verdict Compiler Failed on Clang compiler.  Never have got such a verdict.  Every other compiler submit gets AC. Can't post code here because it is a working solution.

So at first I got AC in 68 ms using scanf("%c", *char)  and then I replaced scanf with_getchar_nolock()  and got AC in 46 ms...

ez

Edited by author 16.09.2015 13:22

my solution WA7, anyone post more test? thanks!

my solution WA7, anyone post more test? thanks!

It seems that lots of people can solve this problem with hashing. Well, I'm using 64 bit hashing and am using sufficiently large prime p (I'm using the usual polynomial hashing i.e. s[0]+s[1]*p+s[2]*p*p ...). I have tried 5 different p's and I'm always catching collisions at test 52 !!! I added code to check for collision and keep working with a different random chosen p ... and now I get TL !!!

My question is: what is the smart solution to the problem that I have? What hashing have you used?

To admins: How can you guys make solutions with random p get collisions? That's probably a really good test. I know how to build anti-hash for certain p, but I cannot imagine a test that hacks 10 random p's in a row. Good job! Or more like "my solution sucks" :)

[code deleted]
-------------------------------------------------------------------------------------
I've got AC.
If you wa on test#3 , you should wirte your OWN suffix array base on your UNDERSTANDING cause it's too easy .
If you want my help , just send me an e-mail .
adress : ngziming@gmail.com .
-------------------------------------------------------------------------------------
pleased try this data
input:
5
CCCCC
CCCCC
output:
CCCCC
-------------------------------------------------------------------------------------
hint:
remeber to add a no-use char at the last of the string .
-------------------------------------------------------------------------------------

Edited by author 16.08.2012 09:29

i tried to solve this problem with dp. O(N*2) time and O(N) memory:
here is my code
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int  n;

string s,t;

string Longest_common_substr(void)
{

    int place;

    int longest=0;

    vector<int> m(n);

    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            if(s[j]==t[i])
            {
                if(j!=0)m[j]=m[j-1]+1;
                else m[j]=1;
            }
            else m[j]=0;

            if(m[j]>longest)
            {
                longest=m[j];
                place=j-longest+1;
            }
            if(longest==n)return s.substr(place,longest);
        }
    }
    if(longest==0)return "";
    else return s.substr(place,longest);



}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie();
    cin>>n;
    cin>>s;
    cin>>t;
    cout<<Longest_common_substr()<<endl;
    return 0;
}

can you please suggest any modifications?

Some new tests were added. 127 authors lost their AC.

my algo Accepted in 0.4s.

Edited by author 23.05.2012 16:24

17
WEARECHAMPIONSYES
WEHAVECHAMPIONSNO

What should I write in this case ???
Sory my english


Edited by author 10.04.2011 23:15