/*
Online Java - IDE, Code Editor, Compiler

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

import java.util.*;

public class Main 
{
    static long permutations;
    
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        //TEST CASE 1: findAnagrams("cbaebabacd","abc");
        //String p="abc";
        //String s="cbaebabacd";
        
        //TEST CASE 2:  findAnagrams("abab","ab");
        //String p = "ab";
        //String s = "abab";
        
        //TEST CASE 3: findAnagrams("azazazazazazzzzaaazazazaz", "az")
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazaz";
        
        //TEST CASE 4: findAnagrams("azazazazazazzzzaaazazazpp", "az");
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazpp";
        
        //TEST CASE 5: findAnagrams("abcbcacab", "abc");
        String p = "abc";
        String s = "abcbcacab";
        
        int originalNumber=p.length();
        int n=originalNumber;
        int r = p.length();
        Map <Integer, Long> m = new HashMap<>();
        
        Permutation perm = new Permutation();
        n=originalNumber;
        
        perm.Permutations (n,r,originalNumber, m);
        permutations = perm.getPermutations();
        findAnagrams(s,p);
    }
    
    public static void findAnagrams(String s, String p)
    {
        Set <Integer> stRandomNums = new HashSet<>();
        
        int pos=0;
        int subsetNumber=1;
        Set <String> st = new HashSet<>();
        StringBuilder sb = new StringBuilder(p);
        int startPos=0;
        boolean hasCharFound=false;
        int counter=0;
        StringJoiner sj;
        int temp1;
        Random rand = new Random();
        String[] valuesSet; 
        String []backupValuesSetBeforeModification;
        int num;
        int count=0;
        int subsetEntry=1;
        int cycles=0;
        int totalcycles=0;
        int difference = 0;
        List <String> backupValuesSet = new ArrayList<>();
        int currentSetSize;
        int newSetSize;
        int n;
            
        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);
        }
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            sj=new StringJoiner("");
        
            for (int m=0;m<p.length();m++)
            {
                temp1 = rand.nextInt(p.length());
                currentSetSize=stRandomNums.size();
                stRandomNums.add(temp1);
                
                if (m==0)
                {
                    System.out.println("random num: " + temp1);
                    sj.add(Character.toString(p.charAt(temp1)));
                }
                else
                {
                    if (stRandomNums.size()==currentSetSize)
                    {
                        m=m-1;
                    }
                    else
                    {
                        System.out.println("random num: " + temp1);
                        sj.add(Character.toString(p.charAt(temp1)));
                    }
                }
            }
            stRandomNums.clear();
            
            System.out.println("\n");
            currentSetSize=st.size();
            
            st.add(sj.toString());
            sj=new StringJoiner("");
            newSetSize = st.size();
            cycles++;
            totalcycles++;
           
        }while (newSetSize<permutations);

        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        
        System.out.println("******************Contents of the backup set");
        System.out.println("******************Contents of the valuesSet");
        
        for (String g: valuesSet)
        {
            System.out.println("Subset " + subsetNumber+": " + g);
            subsetNumber++;
        }
        subsetNumber=1;
        
               
        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size() +"\n");
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                System.out.println("\n\n"+valuesSet[entry] + "\t\tSubset: " + subsetEntry  + "  at cycle number: " + totalcycles);
                
                subsetEntry++;
            
                sb=new StringBuilder(valuesSet[entry]);
        
                while(p.length()+startPos<s.length())
                {
                    do
                    {
                        startPos=counter;
            
                        for (int i=startPos; i<s.length();i++)
                        {
			    
                            if(!sb.toString().isEmpty())
                            {
                                System.out.println("This is STARTPOS: " + startPos);
                                System.out.println("This is sb length: " + sb.length());
                                System.out.println("This is s length: " +  s.length());
                            }
                            
                            if (hasCharFound)
                            {
                                pos=0;
                            }
                        
                            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)+")");
				
				System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,(startPos+p.length())));                    
                                                              
                                if (Character.toString(s.charAt(i)).indexOf(sb.toString().charAt(pos))==0)
                                {
                                    System.out.println("char found: " + sb.toString().charAt(pos) + 
                                    "    at index: " + i);
                               
                                    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;
                                }
                                else
                                {
                                    System.out.println("NO MATCH FOUND");
                                    System.out.println("StringBuilder being emptied: " + sb.toString());
                                    sb.delete(0,sb.length());
                                    hasCharFound=false;
                                    break;
                                }
                            }
                            pos++;
                         
                            if (pos==p.length())
                            {
                                pos=0;
                                break;
                            }
                        }
                    }while(!sb.toString().isEmpty());
        
                    if (sb.toString().isEmpty() && hasCharFound)
                    {
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos,(startPos+p.length())) + " is an anagram of: " + valuesSet[entry] 
                        + "\t\t\tIndex("+counter+")");
                        System.out.println("**********************************************************");
                    }
		    if (sb.toString().isEmpty() && !hasCharFound)
                    {
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos,(startPos+p.length())) + " is NOT an anagram of: " + valuesSet[entry] 
                        + "\t\t\tIndex("+counter+")");
                        System.out.println("**********************************************************");
                    }
			
                    System.out.println("*****RESTORING BACKUP OF STRINGBUILDER (String p): " + valuesSet[entry]);
                    pos=0;
            
                    sb=new StringBuilder(valuesSet[entry]);
                    hasCharFound=false;
                    counter++;
                }
                counter=0;
                startPos=0;
            }
        }
        difference = newSetSize;
    }
}
    
class Permutation
{
    static long result=0;
    static int n;
    static int r;
    static int originalNumber;
    
    public long getPermutations()
    {
        System.out.println("***PERMUTATIONS***  nPr (without replacement)");
        System.out.println("P(n,r) = n! / (n−r)!");
        System.out.println("P(" + originalNumber+","+r+") = " + originalNumber+"!" + " / " + "("+originalNumber+"-"+r+")!");
        System.out.println(result);
        
        return result;
    }
     
    public static long Permutations (int n, int r, int originalNumber, Map factorialResults)
    {
        Permutation.n=n;
        Permutation.r=r;
        Permutation.originalNumber=originalNumber;
       
        int temp;
        int denominator;
        
        if (originalNumber<r || r<0)
        {
            System.out.println("please enter n ≥ r ≥ 0");
            System.exit(0);
            
            return 0;
        }
        if (n>=1)
        {
            result = (n* (Permutations (n-1, r,originalNumber, factorialResults))); // this completes factorial for numerator
            factorialResults.put(n,result);
            
            if (n==originalNumber)
            {
                denominator = originalNumber-r;
                if (factorialResults.containsKey(denominator))
                {
                    factorialResults.get(denominator);
                    return result / (long)factorialResults.get(denominator);
                }
            }
            return result;
        }
        return 1;
    }
}