Please Help ! Getting RE(NZEC) (Java)

Getting RE(NZEC) (Java)

Here is my Code !!

    import java.io.*;


    public class MainRE 

    {

    static String a;
    
    static String b;
    
    static private int ls[][];
    
    static int arr[];
    
    static int L;

    public static void main(String[] args) throws IOException
    
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCount =Integer.parseInt(br.readLine());

        for (int i = 1; i <= testCount; i++)
        {
            try
            {
                a=br.readLine();
                b=br.readLine();
                L=Integer.parseInt(br.readLine());
                arr=new int [L];
                initDp();
                printLs();
            }
            catch(Exception e)
            {
                break;
                
            }
        }

    }

    public static void printLs() 
    {
        for (int i = 0; i <= a.length(); i++) 
        {
            for (int j = 0; j <= b.length(); j++) 
            {
                if(ls[i][j]>0)updatearr(ls[i][j]);
            }
        }
        for(int z=0;z<arr.length;z++)
        {
            System.out.print(arr[z]);
            if(z<arr.length-1)System.out.print(" ");

        }
        System.out.println();     
    }

    public static void updatearr(int n)
    {
        for(int z=0;z<arr.length;z++)
        {
            if(n>=(z+1))arr[z]++;
        }
    }

    private static void initDp()
    {
        ls = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++)
            ls[i][0] = 0;

        for (int j = 0; j <= b.length(); j++)
            ls[0][j] = 0;

        for (int i = 1; i <= a.length(); i++) 
        {
            for (int j = 1; j <= b.length(); j++)
            {
                ls[i][j] = (a.charAt(i - 1) != b.charAt(j - 1)) ? 0 : ls[i - 1][j - 1] + 1;
            }
        }
    }

}
1 Like

ur algo may be 100% correct…but the problem here is the constraint on the length of the strings…you cannot create a matrix of size (2 * 10^5) * (2 * 10^5)…that is lot of memory…hence ur getting RE…i would suggest that u should think of another method to solve this problem…:slight_smile:

even a string length around 5000 will give u SIGSEGV…!!!

EDIT

if u want to do it by this method then you can divide the longer string into sub-parts and then apply this logic…assume strings a,b.

in this method instead of making an array of (b.length+1) * (a.length+1) you can make an array of (b.length+1) * (const+1)(considering length of b is less than or equal to length of a) where const is any number that will not exceed the memory limit!!!

as before u write the string b horizontally and string a vertically…but just a change is that always keep only “const” letters of string a vertically…then apply ur lcs algo…then calc number of pos where values greater than or equal to the variable z…then replace the last row of the array with the first row and then apply lcs with the next “const” letters of string a till it gets exhausted…maybe this will pass…hope this helps…:slight_smile:

2 Likes

But its working for Subtask 3(15 points) where length of any string is at most 200 !!
Its showing RE(NZEC) for Subtask 1(15 points),Subtask 2(20 points) !

ya…m seeing that…give me some time…:slight_smile:

in subtask 1 and 2 there is no limit on the length of the string…only limit is on L…so maybe the length can be upto 2 * 10^5

see this soln…http://www.codechef.com/viewsolution/2410351

this proves that in subtask 1 and 2 lengths have no special constraints…!!!

//