Question

How to find all occurrences of all substring permutations (anagrams) in a string with Java

Answer 1

import java.util.List;
import java.util.ArrayList;

public class MyClass {
    private static int SIZE = 256;
 
    private static boolean Compare(char[] arr_str, char[] arr_sub) {
        for (int i = 0; i < SIZE; ++i) {
            if (arr_str[i] != arr_sub[i])
                return false;
        }
     
        return true;
    }
 
    public static List<Integer> find_substring_permutations(String str, String sub) {
        List<Integer> result_list = new ArrayList<>();
         
        char[] countSub = new char[SIZE];
        char[] countStr = new char[SIZE];
     
        for (int i = 0; i < sub.length(); i++) {
            (countSub[sub.charAt(i)])++;
            (countStr[str.charAt(i)])++;
        }
 
        for (int i = sub.length(); i < str.length(); i++) {
            if (Compare(countSub, countStr))
                result_list.add(i - sub.length());
     
            countStr[str.charAt(i)]++;
            countStr[str.charAt(i - sub.length())]--;
        }
     
        if (Compare(countSub, countStr))
            result_list.add(str.length() - sub.length());
     
        return result_list;
    }
    public static void main(String args[]) {
        // 0 CBA : 5 BAC : 11 ABC : 12 BCA : 13 CAB : 21 ACB : 26 CAB
        String s = "CBAxyBACdarABCABbcapoACBqtCAB"; 
        String sub = "ABC";
         
        List<Integer> result = find_substring_permutations(s, sub);
 
         System.out.println(result.toString());
    }
}
 
 
 
 
/*
run:
 
[0, 5, 11, 12, 13, 21, 26]
 
*/

 

70+ SQL courses for beginners and professionals