Created
December 15, 2012 16:42
-
-
Save markkcc/4296955 to your computer and use it in GitHub Desktop.
Solution in Java to Problem C. "Encrypted Password" from Arab Collegiate Programming Contest (ACPC) 2012.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.File; | |
| import java.io.FileNotFoundException; | |
| import java.util.Scanner; | |
| public class password { | |
| public static void main(String[] args) throws FileNotFoundException { | |
| Scanner scan = new Scanner(new File("password.in")); | |
| int cases = scan.nextInt(); | |
| for(int qq = 0; qq < cases; qq++) { | |
| String str = scan.next(); | |
| String pass = scan.next(); | |
| int[] count = new int[26]; | |
| int[] solution = new int[26]; | |
| //get the character count of the solution | |
| for(int i = 0; i < pass.length(); i++) | |
| solution[pass.charAt(i) - 'a']++; | |
| //get character counts for the first part of the whole string | |
| for(int i = 0; i < pass.length(); i++) | |
| count[str.charAt(i) - 'a']++; | |
| //compare both arrays to see if character counts match | |
| if(checkMatch(count, solution)) { | |
| System.out.println("YES"); | |
| continue; //if this is a solution, go to the next test case | |
| } | |
| else if(str.length() == pass.length()) { | |
| System.out.println("NO"); | |
| continue; | |
| } | |
| //continue checking for the whole string for possible matches | |
| for(int i = pass.length(); i < str.length(); i++) { | |
| count[str.charAt(i - pass.length()) - 'a']--; | |
| count[str.charAt(i) - 'a']++; | |
| if(checkMatch(count, solution)) { | |
| System.out.println("YES"); | |
| break; | |
| } | |
| else if(i == str.length() - 1) | |
| System.out.println("NO"); | |
| } | |
| } | |
| } | |
| public static boolean checkMatch(int[] a, int[] b) { | |
| for(int i = 0; i < a.length; i++) | |
| if(a[i] != b[i]) | |
| return false; | |
| return true; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment