/*
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");
        
        //TEST CASE 2:
        //findAnagrams("abab", "ab");
        
        //TEST CASE 3:
        //findAnagrams("azazazazazazzzzaaazazazaz", "az");
        
        //TEST CASE 4:
        //findAnagrams("azazazazazazzzzaaazazazpp", "az");
    }
    
    public static void findAnagrams(String s, String p)
    {
        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"
        int[][] minMaxIndexes = new int[s.length()][(p.length()*s.length())];
        int[][] store = new int[s.length()][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++)
                {
                    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: " + s.charAt(s.substring(startPos,p.length()).indexOf(p.charAt(pos))));
                        
                                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 Minimum: " + minimum);
                                
                                System.out.println(startPos);
                                System.out.println(temp);
                                minMaxIndexes[startPos][temp]=minimum;
                                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);
                                //startPos++;
                                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("NO MATCH FOUND");
                                
                                //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 of : " + s);
                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.
        
        }while(p.length()+startPos<s.length());
        
        minimum=minMaxIndexes[0][1] - minMaxIndexes[0][0];
        maximum=minMaxIndexes[0][1] - minMaxIndexes[0][0];
        
        for (int k=0;k<numMatchesSmallWindow;k++)
        {
            //we know all values are stored like this
            //it contains for each startpos all the indexes that match with String p
            //I would need to navigate array and ascertain the minimum/maximum for each row
            //The value would then go into a repository.
            //minimum = (startPos+s.substring(startPos,s.length()).indexOf(sb.toString().charAt(pos)));
            //minMaxIndexes[startPos][temp]=minimum;
            
            if ((minMaxIndexes[k][0])<=minimum)
            {
                minimum=minMaxIndexes[k][0];
            }
            
            if ((minMaxIndexes[k][0])>=maximum)
            {
                maximum=minMaxIndexes[k][1];
            }
        }
        
        for (int m=0; m<store.length;m++)
        {
            for (int n=0; n<store[m].length;n++)
            {
                System.out.println("**********************************************************");
        System.out.println(p + " is found in the smallest window of : " + s.substring(store[m][n],store[m][n]) + "\t\tIndex("+store[m]+" - " + store[n]+")");
        System.out.println("**********************************************************");
    
                
            }
        }
             
        
    }
}