Massive Algorithms: Anagram Substring Search (Or Search for all permutations)

Anagram Substring Search (Or Search for all permutations) | GeeksforGeeks

Anagram Substring Search (Or Search for all permutations) | GeeksforGeeks
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.
Expected time complexity is O(n)
Key Algorithm: Rabin Karp Algorithm
In praticle interview, we are unlike to write real, complete Rabin Karp or Boyer Moore Algorithm, as it' complicate, but we may use its variant, same/simliar idea to solve the problem.

1) The first count array store frequencies of characters in pattern.
2) The second count array stores frequencies of characters in current window of text.

The important thing to note is, time complexity to compare two count arrays is O(1) as the number of elements in them are fixed (independent of pattern and text sizes). Following are steps of this algorithm.
1) Store counts of frequencies of pattern in first count array countP[]. Also store counts of frequencies of characters in first window of text in array countTW[].

2) Now run a loop from i = M to N-1. Do following in loop.
…..a) If the two count arrays are identical, we found an occurrence.
…..b) Increment count of current character of text in countTW[]
…..c) Decrement count of first character in previous window in countWT[]

3) The last window is not checked by above loop, so explicitly check it.

#define MAX 256 

// This function returns true if contents of arr1[] and arr2[]

// are same, otherwise false.

bool compare(char arr1[], char arr2[])

{

    for (int i=0; i<MAX; i++)

        if (arr1[i] != arr2[i])

            return false;

    return true;

}
// This function search for all permutations of pat[] in txt[]

void search(char *pat, char *txt)

{

    int M = strlen(pat), N = strlen(txt);

    // countP[]:  Store count of all characters of pattern

    // countTW[]: Store count of current window of text

    char countP[MAX] = {0}, countTW[MAX] = {0};

    for (int i = 0; i < M; i++)

{

        (countP[pat[i]])++;

        (countTW[txt[i]])++;

}

    // Traverse through remaining characters of pattern

    for (int i = M; i < N; i++)

{

        // Compare counts of current window of text with

        // counts of pattern[]

        if (compare(countP, countTW))

            cout << "Found at Index " << (i - M) << endl;

        // Add current character to current window

        (countTW[txt[i]])++;

        // Remove the first character of previous window

        countTW[txt[i-M]]--;

}

    // Check for the last window in text

    if (compare(countP, countTW))

        cout << "Found at Index " << (N - M) << endl;

}

Java code: http://ideone.com/c36gWy
http://segmentfault.com/a/1190000003889540

用一个256位的数组统计Pattern字符串中每一个字符出现的次数，然后同理，维护一个长度为Pattern长度的窗口，来统计这个窗口里母串各个字符出现的次数，计入一个数组中。比较这两个数组是否相同就知道是否是变形词子串了。窗口向右移动一位时，加上新来的字符，减去刚离开窗口的字符。

    public static List<Integer> findSubstring(String str, String ptn){
        List<Integer> res = new LinkedList<Integer>();
        // 一个数组统计Pattern的字符出现次数
        int[] pntcnt = new int[256];
        // 一个数字统计窗口内的字符出现次数
        int[] strcnt = new int[256];
        for(int i = 0; i < ptn.length(); i++){
            pntcnt[ptn.charAt(i)]++;
        }
        int i = 0;
        for(i = 0; i < ptn.length() && i < str.length(); i++){
            strcnt[str.charAt(i)]++;
        }
        if(isSame(pntcnt, strcnt)){
            res.add(i - ptn.length());
        }
        while(i < str.length()){
            // 新来一个字符，自增其出现次数
            strcnt[str.charAt(i)]++;
            // 将离开窗口的字符次数减一
            strcnt[str.charAt(i - ptn.length())]--;
            i++;
            // 判断两个数组是否相同
            if(isSame(pntcnt, strcnt)){
                res.add(i - ptn.length());
            }
        }
        return res;
    }
    
    public static boolean isSame(int[] arr1, int[] arr2){
        if(arr1.length != arr2.length) return false;
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] != arr2[i]) return false;
        }
        return true;
    }

http://www.zrzahid.com/find-anagram-of-a-string-in-another-string/
May overflow.

Assign each of the 26 letters a unique prime number i.e. {‘a’=>2, ‘b’=>3, ‘c’=>5, ‘d’=>7, ‘e’=>11, …, ‘l’ = 37, …, ‘s’ => 67, …. ,’t’ => 71,…. ‘z’ => 101}. In order to extend, If we have 8 byte character then we will use first 256 primes.
All the anagrams of a word will have the same UNIQUE product of primes assigned to each character. For example: prod(“tea”) = prod(“tae”) = prod(“eat”) = prod(“eta”) = prod(“ate”) = prod(“aet”)= 71*11*2 = 1562. Find prime product of the needle.
Now, go through each position of the haystack and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
while passing through the letters of the haystack check if the current cum-prod is divisible by the needle product value. If it is then it means we found an anagram! The anagram ends at the current position having a length equal to needle length. So, we can get the substring in relatively constant time if haystack size is significantly larger than the needle.

private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

public static Set<String> findAnagramicSubString(final String str, final String pattern) {
    final String haystack = str.toLowerCase();
    final String needle = pattern.toLowerCase();
    final Set<String> substrings = new HashSet<String>();

    long needleKey = 1;
    for (int i = 0; i < needle.length(); i++) {
        needleKey *= primes[needle.charAt(i) - 'a'];
    }

    final Map<Long, Integer> cumprods = new HashMap();

    long cumprod = 1;
    for (int i = 0; i < haystack.length(); i++) {
        cumprod *= primes[haystack.charAt(i) - 'a'];
        if (cumprod % needleKey == 0 && cumprods.containsKey(cumprod / needleKey)) {
            substrings.add(haystack.substring(i - needle.length() + 1, i + 1));
        }

        cumprods.put(cumprod, i);
    }

    substrings.remove(needle);
    return substrings;
}

http://geekilyyours.blogspot.com/2014/08/commentimport-java.html
Should use rolling hash

    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;

}

Given a dictionary and a word. Find all the anagrams of the given word in the dictionary.

public static Set<String> findAllAnagramsInDictionary(final Set<String> dictionary, final String word) {
    final Set<String> anagrams = new HashSet<String>();
    final long wordKey = getPrimeProduct(word);
    for (final String dictionaryWord : dictionary) {
        if (wordKey == getPrimeProduct(dictionaryWord)) {
            anagrams.add(dictionaryWord);
        }
    }

    return anagrams;
}

http://www.zrzahid.com/find-anagram-of-a-string-in-another-string/

Sliding Histogram Approach – O(n) time O(1) space
Notice that when we find an anagram starting from i we might potentially find another starting from i+1 if character count distribution remains same. For example, text = “abaab” and pattern = “aba”. We can see both of the strings have same character count distribution i.e. histogram ([a=2,b=1,c=0,..]) for first m characters, where m=length of pattern. If we remove first character ‘a’ and add 4th character ‘a’ then histogram remains same ([a=2,b=1,c=0,..]).

So, we can create a fixed length (=size of the pattern) sliding window histogram for characters in text string and check if the window equals to the pattern histogram at each position of the text. We keep sliding the window to right one position and check if the window equals to patten histogram. This is linear time algorithm if the alphabet size of the strings is finite (for example 256 character set). Below is the implementation of the idea in O(n) time and O(1) space.

private static boolean equalHistogram(int[] hist1, int[] hist2){
 for(int i = 0; i < hist1.length; i++){
  if(hist1[i] != hist2[i]){
   return false;
  }
 }
 
 return true;
}

public static int searchAnagramSubstring(String text, String pattern){
 int count = 0;
 int n = text.length();
 int m = pattern.length();
 
 if(n < m | m == 0 | m == 0){
  return 0;
 }
  
  
 int textHist[] = new int[256];
 int patHist[] = new int[256];
 
 //initial histogram window of size m 
 int i = 0;
 for(i = 0; i < m; i++){
  patHist[pattern.charAt(i)]++;
  textHist[text.charAt(i)]++;
 }

 //search the pattern histogram in a sliding window of text histogram
 do{
  //O(1) time check as array size is constant
  if(equalHistogram(textHist, patHist)){
   System.out.println("anagram found : "+text.substring(i-m, i));
   count++;
  }
  
  //slide the text histogram window by 1 position to the right and check for anagram
  textHist[text.charAt(i)]++;
  textHist[text.charAt(i-m)]--;
 } while(++i < n);
 
 return count;
}

Mathematical Approach – O(n) time O(1) space

private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

public static Set<String> findAnagramicSubString(final String str, final String pattern) {
    final String haystack = str.toLowerCase();
    final String needle = pattern.toLowerCase();
    final Set<String> substrings = new HashSet<String>();

    long needleKey = 1;
    for (int i = 0; i < needle.length(); i++) {
        needleKey *= primes[needle.charAt(i) - 'a'];
    }

    final Map<Long, Integer> cumprods = new HashMap();

    long cumprod = 1;
    for (int i = 0; i < haystack.length(); i++) {
        cumprod *= primes[haystack.charAt(i) - 'a'];
        if (cumprod % needleKey == 0 && cumprods.containsKey(cumprod / needleKey)) {
            substrings.add(haystack.substring(i - needle.length() + 1, i + 1));
        }

        cumprods.put(cumprod, i);
    }

    substrings.remove(needle);
    return substrings;
}

There could be a variant of this problem.

Given a dictionary and a word. Find all the anagrams of the given word in the dictionary.

Following is an O(n) solution with constant space. The idea is to create a hash function that will return same value for anagrams of a word. We can build such a hash using he character histogram of a word.

public class Dictionary{
 private Set<String> dictionary = new HashSet<String>();
 
 public void add(String word){
  dictionary.add(word);
 }
 public void addAll(List<String> words){
  dictionary.addAll(words);
 }
 public boolean remove(String word){
  return dictionary.remove(word);
 }
 private String getKey(String str){
  str = str.toLowerCase().trim();
  int[] hist = new int[256];
  for(int i = 0; i < str.length(); i++){
   hist[str.charAt(i)]++;
  }
  
  StringBuilder sb = new StringBuilder();
  
  for(int val : hist){
   sb.append(val);
  }
  
  return sb.toString();
 }
 public int searchAnagram(String pattern){
  int count = 0;
  HashMap<String, List<String>> histogramMap = new HashMap<String, List<String>>();
  
  for(String word : dictionary){
   String key = getKey(word);
   
   if(!histogramMap.containsKey(key)){
    histogramMap.put(key, new ArrayList<String>());
   }
   
   histogramMap.get(key).add(word);
  }
  
  String searchKey = getKey(pattern);
  List<String> res = histogramMap.get(searchKey);
  
  if(res != null){
   count = res.size();
   
   System.out.print("anagrams in dict: ");
   for(String s : res){
    System.out.print(s+" ");
   }
   System.out.println();
  }
  
  return count;
 }
}

http://coding-interview-archives.blogspot.com/2013/09/find-all-occurrences-of-all.html
Read full article from Anagram Substring Search (Or Search for all permutations) | GeeksforGeeks

Anagram Substring Search (Or Search for all permutations) | GeeksforGeeks

Labels

Popular Posts