Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] and its permutations (or anagrams) in txt[]. You may assume that n > m.E.g. : I/p : txt[] = “BACDGABCDA” pat[] = “ABCD”o/p :0,5,6
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; /** * Created by Arun on 8/9/14. */ public class PatternMatching { public static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i < Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static ArrayList<Integer> getPrimes() { ArrayList<Integer> arr = new ArrayList<Integer>(); for(int i=0, j=0;j<26;i++){ if(isPrime(i)){ arr.add(i); j++; } } return arr; } private static ArrayList<Integer> matchPattern(String str, String pattern) { ArrayList<Integer> a = getPrimes(); String alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; Map<String, Integer> valMap = new HashMap<String, Integer>(); int patternProduct = 1; for(int i=0;i<alphabets.length();i++) { valMap.put(String.valueOf(alphabets.charAt(i)), a.get(i)); } for(int i=0;i<pattern.length();i++) { patternProduct = patternProduct * valMap.get(String.valueOf(pattern.charAt(i))); } for(int i=0;i<=str.length()-pattern.length();i++) { int tempVal=1; for(int j=i, k=0;k<pattern.length();k++,j++){ tempVal = tempVal * valMap.get(String.valueOf(str.charAt(j))); } if(tempVal==patternProduct) { System.out.println(i); } } return null; } public static void main(String args[]) { matchPattern("BACDGABCDABCD", "ABCD"); } }
No comments:
Post a Comment