/*
Online Java - IDE, Code Editor, Compiler

Online Java is a quick and easy tool that helps you to build, compile, test your programs online.
*/

public class Main 
{
    static StringBuilder sb;
    
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        //TEST CASE 1:
        //findAnagrams("cbaebabacdabc", "abc");
        
        //findAnagrams("cbaeacb", "abc");
        //findAnagrams("abmbafcvbacabc", "abc");
        
        //findAnagrams("cbaeacb", "abc");
        
        //****SEE Documentation on workaround******
        //There might be other test cases failing similarly
        //findAnagrams("cabc", "abc"); //failing
        //findAnagrams("abmbafcvbacabc", "abc");
        
        //findAnagrams("cabc", "ab");
        
        //TEST CASE 2:
         findAnagrams("abab", "ab");
        
        //TEST CASE 3:
        //findAnagrams("azazazazazazzzzaaazazazaz", "az");
        
        //TEST CASE 3:
       //findAnagrams("CODEBANC", "BANC");
        
        
        //TEST CASE 4:
        //findAnagrams("attaczc", "attz");
    }
    
    public static void findAnagrams(String s, String p)
    {
        int backupTemp;
        int location=0;
        int temp=0;
        int minimum=0;
        int maximum=0;
        sb=new StringBuilder(p);
        int startPos=0;
        boolean hasCharFound=false;
        int counter=0;
        int numMatchesSmallWindow=0;
        int pos=0;
        
        //we can assume that there can be indexes
        //min and max for each element on String s
        //for instance String s="aaaaaaa" String p="a"
        
        //****FIRST DIMENSION - ROW****
        //[This will hold the startPos, it can be any index for s.length()] 
        //SECOND DIMENSION - COL
        //[This will hold the index to where character in String p appears in String s] 
        
        //we know that there can be lots of index matches
        //since we continuously test each character in String p against String s
        //against every possible startPos. So we have to provision for
        //large number of rows. the maximum can not be any greater than below.
        //although we would expect rows to get less and less once startPos increases
        //I am creating sufficient storage anyhow
        int[][] minMaxIndexes = new int[(p.length()*s.length())][2];
        
        int[][][] store = new int[s.length()][1][2];
        
        System.out.println("String (s) to search in: " + s);
        System.out.println("String (p) template word: " + p);
        
        if (s.length()<p.length())
        {
            System.out.println("template word is longer length than main String");
            System.exit(0);
        }
        
        do
        {
            do
            {
                //this is going through the main String...
                //it is starting more inwards once it has processed the entire length of p
                //or if it fails to find a letter in String p within the main string
                //counter has been incremented in this circumstance outside of the inner do while loop
                //it has to be remembered the outer do while loop is when there are insufficient characters in main String
                //to compensate for String p
            
                startPos=counter;
                
                for (int i=startPos; i<s.length();i++)
                {
                    //we keep this here so we have the option to clear any data written into
                    //minMaxIndexes in situations where it commences from startPos and finds matches
                    //against String p. But then there might be no matches available.
                    
                    backupTemp=temp;
                    
                    if(!sb.toString().isEmpty())
                    {
                        System.out.println("\ncounter: " + counter);
                        System.out.println("val i: " + i);
                        System.out.println("This is STARTPOS: " + startPos);
                        System.out.println("This is sb length: " + sb.length());
                    }
                    
                    //we require less than or equal to here
                    //since if the stringbuilder is reduced to a single character (sb.length()=1)
                    //this loop will not increase and remain at 0. 
                    //It will exit the for loop and cause the outer for loop to increase by 1..
                    //So it will impact the screen output to be incorrect for
                    // System.out.println("Checking character: " + sb.toString().charAt(pos) + 
                    //"  against the main String index: " + i + "("+s.charAt(i)+")" 
                    //It will show incorrect string index.
                    //HOWEVER IT WILL NOT IMPACT THE indexOf().  
                    //Even though indexOf relies on the startPos, we can see from above that the value of StartPos
                    //(startPos=counter)
                    //has only changed when it has broken out of the most outer for loop. So this remains unaffected
                    
                    for (pos=0; pos<=sb.length(); pos++)
                    {
                        if (hasCharFound)
                        {
                            pos=0;
                        }
                    
                        //This is included since it will attempt to perform charAt(pos) on an empty StringBuilder 
                        if (!sb.toString().isEmpty())
                        {
                            System.out.println("value of pos: " + pos);
                            System.out.println("value of sb: " + sb.toString());
                            System.out.println("Checking character: " + sb.toString().charAt(pos) + 
                            "  against the main String index: " + i + "("+s.charAt(i)+")" 
                            + " TO index: " + (s.length()-1) +  "("+s.charAt(s.length()-1)+")" );
                    
                            //if there is a match
                            System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,(s.length()-1)));
                            
                            if (s.substring(startPos,s.length()).indexOf(sb.toString().charAt(pos))!=-1)
                            {
                                System.out.println("char found: " + sb.toString().charAt(pos) + 
                                "    at index: " + (startPos+s.substring(startPos,s.length()).indexOf(sb.toString().charAt(pos))));
                                
                                //we know the minimum will be the first match of String p in String s
                                
                                minimum = (startPos+s.substring(startPos,s.length()).indexOf(sb.toString().charAt(pos)));
                                System.out.println("STORING index match: " + minimum);
                                
                                minMaxIndexes[temp][0]=minimum;
                                
                                //need to write this since we know that there might not
                                //necessarily be match on the first character of String s
                                //we know that startPos corresponds to String s
                                minMaxIndexes[temp][1]=startPos;
                                System.out.println("---------------BEING WRITTEN" + "(***temp: " + temp +") index: " 
                                + minimum + "   startpos: " + startPos);
                                //this is the number of times it has performed a write
                                //for an index found
                                temp++;
                                
                                //it removes character from the StringBuilder(which holds String p) 
                                //at index which it found the match
                               
                                System.out.println(sb.toString().charAt(pos) + " has been removed from StringBuilder (String p)" 
                                +  "= "+ sb.toString());
                                sb.deleteCharAt(pos);
                                
                                System.out.println("This is current StringBuilder (String p): " + sb.toString());
                                hasCharFound=true;
                            }
                                //if there is no match found, no need to iterate inner for loop any further
                                //but the outer loop is still relevant since it might find 
                                //anagram starting from one position further in the main string
                
                            else
                            {
                                System.out.println("TESTING999:------------------------------");
                                System.out.println(minMaxIndexes[0][0]);
                                System.out.println(minMaxIndexes[1][0]);
                                System.out.println(minMaxIndexes[2][0]);
                                System.out.println(minMaxIndexes[3][0]);
                                System.out.println(minMaxIndexes[4][0]);
        
                                System.out.println("NO MATCH FOUND");
                                System.out.println("StringBuilder being emptied: " + sb.toString());
                                sb.delete(0,sb.length());
                                
                                //we know at this point, we have already stored values in 
                                //minMaxIndexes. We need to remove all values at row temp
                                //but need to be careful and only process if it has written to the row
                                //ie if found some character matches examining substring on String s
                                //otherwise it will remove previous data....
                                if (temp!=backupTemp && hasCharFound)
                                {
                                    //we know that in this event it has performed
                                    //writing into the array from backupTemp=>temp
                                    
                                    System.out.println("SIZE backupTemp: " + backupTemp);
                                    System.out.println("SIZE Temp: " + temp);
                                    
                                    temp=backupTemp;
                                }
                                
                                //I have removed this since we can perform this operation when the inner do while loop exits
                                //(when the StringBuilder is empty)
                                //startPos++;
                                
                                //if it can not find a match across entire String s
                                //it can exit the application
                                //System.exit(0);
                            }
                        } //if !sb.isEmpty()
                    } 
                    
                    if(!sb.toString().isEmpty())
                    {
                        System.out.println("REACH1-----------------------------");
                        System.out.println("value of i: " + i);
                        System.out.println("value of startPos: " + startPos);
                    }
                    
                } //end of for loop    for (int i=startPos; i<s.length();i++)
                System.out.println("********************");
                //I am changing the exit condition to this...
                //So this effectively means that any areas of code above where it doesn't find an anagram, 
                //it should in practice remove all contents of the StringBuilder.
                //And only once it leaves the while loop, it should aim to restore it again...
            }while(!sb.toString().isEmpty()  /*startPos<=p.length()*/);
            
            System.out.println("REACH2: " + "startPos: " + startPos);
            //at this point we know that it has found an anagram
            //since all characters have been removed
        
            if (sb.toString().isEmpty() && hasCharFound)
            {
                System.out.println("**********************************************************");
                //System.out.println(p + " is found in the small window of : " + "\t\t\tIndex("+(minimum)+" - "+ maximum+")");
                System.out.println(p + " is found in the small window: " + s.substring(startPos,s.length()));
                System.out.println("**********************************************************");
            
                //we know the maximum will be the first match of String p in String s
            }
        
            //we need to restore the original StringBuilder to check further in the String s
        
            System.out.println("*****RESTORING BACKUP OF STRINGBUILDER (String p): " + p);
            sb=new StringBuilder(p);
            
            //maximum=0;
            //minimum=s.length()-1;
        
            hasCharFound=false;
            
            //we also need to make the startPos to be i+1
            //since we are now ready to start anagram check at next position in main String
            //since i has been affected in past execution in relation to startPos, 
            //there should be a counter variable running
            //inside the main for loop... This variable would be incremented.
            counter++;
        
            //this while statement is so that if there are insufficient characters left in s
            //in relation to length of p, there is no point of performing anagram check
            //it is extremely tricky to know if this statement is 100% index perfect.
            //but all are referencing non-zero indexed based values..
            //startPos is no longer zero indexed based when its context is taken out of the indexing above.
        
            /*
            System.out.println("TESTING:------------------------------");
            System.out.println(minMaxIndexes[0][0]);
            System.out.println(minMaxIndexes[1][0]);
            System.out.println(minMaxIndexes[2][0]);
            System.out.println(minMaxIndexes[3][0]);
            System.out.println(minMaxIndexes[4][0]);
            System.out.println(minMaxIndexes[5][0]);
            System.out.println(minMaxIndexes[6][0]);
            System.out.println(minMaxIndexes[7][0]);
            System.out.println(minMaxIndexes[8][0]);
            */
        
        }while(p.length()+startPos<s.length());
        
        //we are here since it is no longer possible for
        //all the characters in String p to appear in String s
        //since the startPos is too far in relation to size of String p
        //and String s
        
        //we are setting this as the least value possible
        //This seems counterintuitive but it has to be visualised that we are
        //seeking to go through each row (corresponding to traversal at each startPos)
        //we want to seek highest index in each row
        //and this will become the new minimum
        minimum=0;
        System.out.println("Smallest window initialised to first index String s:" +"("+s+")" + minimum);
        
        int num=0;
        int smallWindowSize;
        int maximumWindowSizeStartPos;
        
        //we are using temp since we know we have completed
        //temp  writes into minMaxIndexes
        int position=0;
        int[][] storage = new int[p.length()][2];
        int numStores=0;
        int[][] storageMaximum = new int[p.length()*s.length()][2];
        int maxCounter=0;
        boolean hasAddedStorage=false;
        int windowLengthStartPos;
        
        //we get the smallest window sizes for
        
        for (int k=0;k<temp;k++)
        {
            System.out.println("\nSmallest window: " + minimum);
            System.out.println("ROW: " + k +"  Startpos: " + minMaxIndexes[k][1] + 
            " index: " + minMaxIndexes[k][0]);
           
            //smallWindowSize=minMaxIndexes[k][0]-minMaxIndexes[k][1];
           
            //we build up the information for same startPosition in an array
            if (minMaxIndexes[k][1]==minMaxIndexes[k+1][1])
            {
                storage[numStores][0]=minMaxIndexes[k][0];
                storage[numStores][1]=minMaxIndexes[k][1];
                
                if (sb.toString().isEmpty())
                {
                System.out.println("1Added into storage: " + "index:" + storage[numStores][0] + 
                " startPos: " + storage[numStores][1]);
                System.out.println(position);
                hasAddedStorage=true;
                System.out.println(hasAddedStorage);
                numStores++;
                }
            }
            
            else  //startPos differs
            {
                //this would mean that it has different startPos ahead
                if (numStores==0)
                {
                    //This suggests there is only one index information for that
                    //startPos. So we would just perform the storage
                    storage[numStores][0]=minMaxIndexes[k][0];
                    
                    //we need to also keep track of the startPos
                    //otherwise there will be no way to ascertain
                    //small Windows in which the minimum
                    
                    if (sb.toString().isEmpty())
                {
                    //we know the value of StartPos is stored in
                    storage[numStores][1]=minMaxIndexes[k][1];
                    System.out.println("2Added into storage: " + "index:" + storage[position][0] 
                    + " startPos: " + storage[position][1]);
                    System.out.println(position);
                }
                }
                else  //numstores>0
                //we need to get the maximum value from the storage
                {
                    //this can not be here
                    /*
                    if (hasAddedStorage)
                    {
                        storage[numStores][0]=minMaxIndexes[k][0];
                        storage[numStores][1]=minMaxIndexes[k][1];
                        hasAddedStorage=false;
                        System.out.println("3Added into storage: " + "index:" + storage[numStores][0] + " startPos: " + storage[numStores][1]);
                        
                            //numStores++;
                    }
                    
                    */
                }
                    System.out.println("----------------------------------Collated all indexes for startPos: " + storage[position][1]);
                    
                    //maximumWindowSizeStartPos=s.length()-1;
                    
                    //I am totally unsure of this.
                    //If I change to anything else, it pulls wrong values into
                    //storageMaximum...............
                    //I have just left it intact
                    maximum=storage[numStores][0]-storage[numStores][1];
                    
                    System.out.println("SETTING MAXIMUM AS: " + maximum);
                    
                    for (int q=0; q<storage.length;q++)
                    {
                        //in this circumstance we do not add 1 to index position
                        //since both are same.. Instead window size is set to 1 
                        if (storage[q][1]==storage[q][0])
                        {
                            System.out.println("startPos and char both at index 0");
                            windowLengthStartPos=1;
                        }
                        //we need to add 1 to storage[q][1] since it is in zero index
                        else
                        {
                            windowLengthStartPos=storage[q][0]-((storage[q][1]))+1;
                        }
                            
                        System.out.println("$$$$$checking if startPos: "+storage[q][1] 
                        + "\nindex char: " + storage[q][0] + "(WINDOW SIZE: " +windowLengthStartPos+
                        "\nagainst maximum: " + maximum);
                        
                         //at this point, the maximum is calculated wrong
                        //need to use the smallest index value and not the startPos
                        //JUST UNSURE
                        if ((storage[q][0]-storage[q][1])>=maximum)
                        {
                            if ((storage[q][0]-storage[q][1])>maximum)
                            {
                                //THERE WOULD BE A FATAL ERROR IF THE CODE ENTERS
                                //HERE. I WILL LEAVE IT IN MY FINAL CODE
                                //BUT FORCE AN EXIT
                                
                                //we clear all values
                                //storageMaximum = new int[p.length()][2];
                                maxCounter=0;
                                
                                //System.out.println("**************************************************");
                                //System.out.println("CLEARED VALUES IN MAXIMUM STORAGE");
                                //System.out.println("**************************************************");
                                //System.out.println("CODE TO EXIT");
                                //System.exit(0);
                                //this stores the maximum length for that given startPos
                                storageMaximum[maxCounter][0]=(storage[q][0]-storage[q][1]);
                                //this stores the startPos
                                storageMaximum[maxCounter][1]=storage[q][1];
                                System.out.println("**************************************************");
                                System.out.println("maxCounter: " + maxCounter + "  1STORED: " + "startPos: " + storageMaximum[maxCounter][1] + " window size: " + windowLengthStartPos);
                                System.out.println("**************************************************");
                                maximum=storage[q][0]-storage[q][1];
                                
                            }
                            else  //storage[po1]=tion] is equal to maximum
                            {
                                System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
                                //we do not re-initialise the storageMaximum
                                //this stores the maximum length for that given startPos
                                System.out.println("max counter:" + maxCounter);
                                System.out.println("q:" + q);
                                storageMaximum[maxCounter][0]=(storage[q][0]-storage[q][1]);
                                //this stores the startPos
                                storageMaximum[maxCounter][1]=storage[q][1];
                                
                                System.out.println("**************************************************");
                                System.out.println("maxcounter: " + maxCounter + "  2STORED: " + "startPos: " + storageMaximum[maxCounter][1] + "window size: " + windowLengthStartPos);
                                System.out.println("**************************************************");
                                
                                maximum=storage[q][0]-storage[q][1];
                                
                            }
                            maxCounter++;
                        }
                    }
                }
                //these are reset since this will be used in conjunction with store
                //array which is concerned with same startPos
                //we are here since startPos will differ
                numStores=0;
                position=0;
            //}
            location++;
            
            //before we wipe this value, we need to store this value in an array
            //reason is when it processes storageMaximum to display outputs onto the screen
            //it will not know how many writes have been performed.
            //hence it will traverse default values of 0,0 which are stored in 2D array.
            System.out.println("^^^^^^^^^^^^^^^^^^^^NUMBER WRITES:^^^^^^^^^^^^^^^^^^ " + maxCounter);
            
            //if 
            //numberWrites[]
            
            //we need to keep this value in an array.
            //it will allow us to determine how far to traverse in storageMaximum
            //for each of the startPos... We know the array is defined as follows
            //int[][] storageMaximum = new int[p.length()][2];
            //even though p might be small, its still better processing correct elements
            //Alternatively we know that storage[numStores][0] will have the
            //values for startPos taken from minMaxIndexes
            //And the values storageMaximum has assessed if both values are the same,
            //and if so, it has adjusted the window size to be 1.
            //In that respect, when we process storageMaximum, we can simply bypass any results
            //where Window size is 0, since it can not exist....
            
            //maxCounter=0;
            
            //}
        }
        
        String smallWindow;
        int startSmallWindow;
        int endSmallWindow;
        
        System.out.println("TEST!!!!!");
        System.out.println("windows size: " + ((storageMaximum[0][0]-storageMaximum[0][1])+1));
        System.out.println("startPos: " + storageMaximum[0][1]);
        System.out.println("windows size: " + ((storageMaximum[1][0]-storageMaximum[1][1])+1));
        System.out.println("startPos: " + storageMaximum[1][1]);
        System.out.println("window size: " + ((storageMaximum[2][0]-storageMaximum[2][1])+1));
        System.out.println("startPos: " + storageMaximum[2][1]);
        
        int shortestSmallWindow=s.length()-1;
        
        //unfortunately we need to go through all of the arrays again
        //identify the sizes and present it.
        //At the moment in storageMaximum we have the biggest lengths with respect to each
        //startPos..
        //it is the first time that we are genuinely interested in the minimum
        
        System.out.println("\n**********************************************************");
        System.out.println("FINAL RESULT:" + "\t\tString s: " + s + "\t\t\tString p: "+ p);
        System.out.println("**********************************************************");
        
        int lengthWindow;
        
        //System.out.println("this is writes in storageMaximum array: " + maxCounter);
        for (int m=0; m<storageMaximum.length;m++)
        {
            //We now can work out the Substring associated
            //we know that 
           
            startSmallWindow=storageMaximum[m][1];
            endSmallWindow=storageMaximum[m][0];
           
            smallWindowSize=startSmallWindow+endSmallWindow;
            //we know its not possible to have stored anything where both
            //have the same indexes....
            //although strictly speaking it should not be stored in the array, but I had to include this
                
            if (storageMaximum[m][0]==0 && storageMaximum[m][1]==0)
            {
                //This will ensure we are not producing extra results
                if (m==maxCounter)
                {
                    break;
                }
                    
                System.out.println("BROKEN OUT");
                System.out.println("index:" + storageMaximum[m][0]);
                System.out.println("startPos: " + storageMaximum[m][1]);
                m=m+1;
                //break;
            }
           
            smallWindow=s.substring(startSmallWindow,(startSmallWindow+(endSmallWindow+1)));
            //System.out.println("smallWindow: " + startSmallWindow + "  " + "endSmallWindow: " + (startSmallWindow+endSmallWindow) + "  small window: " + smallWindow);
            lengthWindow=((startSmallWindow+endSmallWindow)-startSmallWindow)+1;
            
            //if (lengthWindow>=p.length())
            //{
                System.out.println("**********************************************************");
                System.out.println(p + " is found in the smallest window of : " + smallWindow 
                + "\t\tIndex("+startSmallWindow+" - " + (startSmallWindow+endSmallWindow)+")\tlength Window: " 
                + lengthWindow);
                System.out.println("**********************************************************");
            //}
        }
        
        //do these variables need to be reset?
        //not required if there is execution with one String p
        temp=0;
        minMaxIndexes = new int[s.length()][s.length()];
        store = new int[s.length()][1][2];
        location=0;
    }
}