import java.util.*;
/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 03 - 11
 * 
 * License: Creative Commons
 * 
 * Copyright by Mahsa Sadi
 *
 */

public class AnagramMatcherV3 implements AnagramMatcher {
	
	/**
	 * Problem: 
	 * 
	 * Find All Anagrams in a String
	 * 
	 * 
	 * Description:
	 * 
	 * Given a string s and a non-empty string p, 
	 * find all the start indices of p's anagrams in s.
	 * 
	 * Note:
	 * Strings consists of lower-case English letters only and the length of both strings s and p will not be larger than 20,100.
	 * The order of output does not matter.
	 * 
	 * 
	 * Solution:
	 * 
	 * Definition: An anagram of a string contains all the letters of the string.
	 * However, the order of letters does not matter.
	 * 
	 * Main idea: 
	 * 
	 * Consider a sliding window over s. 
	 * The size of sliding window is the size of p.
	 * Slide this window over s and check whether this window matches p.
	 * If this window matches p, add the start of sliding window to the results.
	 * Otherwise slide (i.e.; move) the window over s. 
	 * 
	 * 
	 * 
	 * 1- Consider a sliding window of size p ( p is the phrase to be found and matched).
	 *    This sliding window always contains p.length characters from s.
	 *    s is the string that is searched.)
	 *    This sliding window moves over s.
	 *    This sliding window initially starts at the beginning of s.
	 *    
	 *    
	 *    
	 *2- Read each letter in the sliding window and match it against the letters of p.
	 *
	 *
	 *
	 *3- If the letter is found in p,
	 *   eliminate that letter from phrase to be checked and go to the next letter in the slidingWindow.
	 *   
	 *   
	 *4- If the letter is not found in p do another check:
	 * 
	 * 
	 *5- Check: Is the letter in p but eliminated previously?
	 *  
	 *    5-1 Yes:
	 *    
	 *      5-1-1: Find the position of the first occurrence of the letter in the sliding window.
	 *      
	 *      5-1-2: Add all the letters between the start of the slidingWindow and that position to 
	 *             the phrase to be checked and matched again.
	 *      5-1-3: Move the beginning of the sliding window to immediately after that position.
	 *      5-1-4: Fill the sliding window with p.length characters.
	 *      
	 *      5-1-5: Resume reading letters one by one and matching against the phrase.
	 *             Go to 2-.
	 *      
	 *   5-2: No:
	 *     5-1: Move the beginning of the sliding window to the position right after the letter.
	 *     5-2: Fill the sliding window with p.length letters.
	 *     5-3: reset the matching phrase to all the letters in p.
	 *     5-4: Resume reading letters one by one and matching against the phrase.
	 *     Go to 2-.
	 *    
	 *     
	 *     
	 * 6- If the sliding window completely matches the phrase,
	 * add the beginning of sliding window to the results.
	 * 
	 * 7- Move the sliding Window one position to the right.
	 * 
	 * 8- Resume Matching. Go to 2-.
	 *   
	 *  
	 
	 */

	@Override
	public List<Integer> findAnagrams(String s, String p) {
		
		List  indices = new ArrayList  ();
		
		int startOfSlidingWindow, endOfSlidingWindow, currentPositionInSlidingWindow;
		startOfSlidingWindow = currentPositionInSlidingWindow = 0;
		
		int slidingWindowLength = p.length();
		
		endOfSlidingWindow  = slidingWindowLength - 1;
		StringBuilder expected = new StringBuilder (p);
		
		
		while (endOfSlidingWindow < s.length())
		{
			
			while (currentPositionInSlidingWindow <= endOfSlidingWindow && endOfSlidingWindow < s.length ())
			{   
			
				char ch = s.charAt(currentPositionInSlidingWindow);
				
				boolean charIsInP = false;
				
				for (int i = 0; i < expected.length(); i++ )
				{
					if (ch == expected.charAt(i))
					{
						charIsInP = true;
						expected.deleteCharAt(i);
						break;
					}
				}
				
				if (charIsInP)
					currentPositionInSlidingWindow++;
				
				else if (!charIsInP)
				{
					boolean charWasInPAndEliminatedBefore = false;
					
					for (int i = startOfSlidingWindow; i < currentPositionInSlidingWindow; i++)
						if (s.charAt(i) == s.charAt(currentPositionInSlidingWindow))
						{
							for (int j = startOfSlidingWindow; j < i; j++)
								expected.append(s.charAt(j));
							
							endOfSlidingWindow = endOfSlidingWindow + ( i - startOfSlidingWindow + 1 );
							startOfSlidingWindow = i + 1;
							currentPositionInSlidingWindow ++;
							
							charWasInPAndEliminatedBefore = true;
							
							break;
						}
					
					
					if (!charWasInPAndEliminatedBefore)
					{
						startOfSlidingWindow = currentPositionInSlidingWindow + 1;
						endOfSlidingWindow = startOfSlidingWindow + slidingWindowLength - 1;
						currentPositionInSlidingWindow = startOfSlidingWindow;
						expected = new StringBuilder (p);
					}
				} 
				
			}
			
			if (endOfSlidingWindow >= s.length())
				break;
			
			else if (expected.length() == 0 )
			{
				indices.add(startOfSlidingWindow);
				expected.append(s.charAt(startOfSlidingWindow));
				startOfSlidingWindow++;
				endOfSlidingWindow++;
				currentPositionInSlidingWindow = endOfSlidingWindow;
				
			}
			
		}
		
		
		return indices;
	}

}