S0.java

S0.java

// Notice: Junit5 as ut framework.
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class S0 {
    public static List<Integer> find(String s, String p) {
        if (s == null || p == null || s.length() == 0 || p.length() == 0 ||
          s.getBytes().length != s.length() || p.getBytes().length != p.length() ||
          s.length() < p.length()) {
            return Collections.emptyList();
        }

        List<Integer> result = new LinkedList<>();

        int[] countMap = new int[Byte.MAX_VALUE];
        Arrays.fill(countMap, -1);
        for (int i = 0; i < p.length(); ++i) {
            byte code = (byte) p.charAt(i);
            if (countMap[code] == -1) {
                countMap[code] = 0;
            }
            countMap[code] += 1;
        }


        int[] usedMap = new int[Byte.MAX_VALUE];

        int matchCount = 0;
        int overCount = 0;
        int matchLength = p.length();

        for (int i = 0; i < s.length(); ++i) {
            if (i >= matchLength) {
                char headCode = s.charAt(i - matchLength);
                if (countMap[headCode] != -1) {
                    if (usedMap[headCode] > countMap[headCode]) {
                        overCount -= 1;
                    }
                    matchCount -= 1;
                    usedMap[headCode] -= 1;
                }
            }

            char code = s.charAt(i);
            if (countMap[code] != -1) {
                matchCount += 1;
                usedMap[code] += 1;
                if (usedMap[code] > countMap[code]) {
                    overCount += 1;
                }
                if (matchCount == matchLength && overCount == 0) {
                    result.add(i - matchLength + 1);
                }
            }
        }
        return result;
    }

    static String findHelper(String s, String p) {
        return find(s, p).stream().
          map(String::valueOf).
          collect(Collectors.joining(","));
    }


    @Test
    public void testFind() {
        assertEquals("", findHelper("", "abc"));
        assertEquals("", findHelper("abc", null));
        assertEquals("", findHelper("abcabcabc", "def"));
        assertEquals("0,6", findHelper("cbaebabacd", "abc"));
        assertEquals("0,5", findHelper("aabcdbcaa", "bcaa"));
        assertEquals("0,1,2,7,8", findHelper("aaaaaabaaaaa", "aaaa"));
        assertEquals("3,4,13", findHelper("asdbacabsadfdabac", "aabc"));
        assertEquals("3,4,13", findHelper("abdbacabsadfdabac", "bcaa"));
    }
}