Anagram Substring Search

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.

1) Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"   Output:   Found at Index 0 Found at Index 5 Found at Index 62) Input: txt[] =  "AAABABAA" pat[] = "AABA"   Output:   Found at Index 0 Found at Index 1 Found at Index 4

统计字母频率

复杂度

时间 O(NM) 空间 O(1)

思路

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

代码

public class AnagramSubstring {        public static void main(String[] args){        System.out.println(findSubstring("BACDGABCDA", "ABCD"));}        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;    }}