import java.util.regex.*;
import java.util.ArrayList;

public class Main {
    private static Pattern combineRe(Pattern p1, Pattern p2){
        return Pattern.compile(combineRE(p1.pattern(), p2.pattern()));
    }
    private static String combineRE(String p1, String p2){
        return combineRE(p1, p2, true);
    }
    private static String combineRE(String p1, String p2, boolean anchors){
        int groups1 = 0, groups2=0;
        StringBuilder newP = new StringBuilder((anchors)?"^(?=":"(?=");
        newP.append(p1);
        if (anchors) newP.append('$');
        newP.append(")(?=");
        
        Pattern capturingGroup = Pattern.compile("(?<!\\\\)(\\\\\\\\)*\\((?!\\?)");
        Matcher m = capturingGroup.matcher(p1);
        while(m.find()) groups1 ++;
        
        m = capturingGroup.matcher(p2);
        
        while(m.find()) groups2 ++;
        String new2 = p2;
        
        for(int i=1; i<=groups2; i++)
            new2 = new2.replaceAll("(?<!\\\\)\\\\"+i, "\\\\" + (i+groups1));
                
        newP.append(new2);
        if (anchors) newP.append('$');
        newP.append(')');
        if (anchors) newP.append(".*");
        return newP.toString();
    }
    private static String[] findAllCombinedRE(String p1, String p2, String haystack, boolean overlap){
        ArrayList<String> toReturn = new ArrayList<String>();
        Pattern pCombo = Pattern.compile(combineRE(p1,p2, false));
        String pComboMatch = combineRE(p1,p2, true);
        Matcher m = pCombo.matcher(haystack);
        int s = 0;
        while (m.find(s)){
            s = m.start()+1;
            String match = haystack.substring(m.start());
            for (int i=match.length(); i>0; i--){
                String sMatch = match.substring(0,i);
                if (Pattern.matches(pComboMatch, sMatch)){
                    toReturn.add(sMatch);
                    if (!overlap){
                        s = m.start()+i;
                        break;
                    }
                }
            }
        }
        return toReturn.toArray(new String[]{});
        
    }
    public static void main(String[] args){
        String p1 = "a.*";
        String p2 = ".*b";
        String p = combineRE(p1, p2);
        String s = "caabcbc";
        System.out.println("p1: " + p1 + "\np2: " + p2 + "\np: " + p + "\ns: " + s);
        Matcher m = Pattern.compile(p).matcher(s);
        m = Pattern.compile("(?=4)").matcher("01234567890123456");
        String[] noverlap = findAllCombinedRE(p1, p2, s, false);
        for (int i=0; i<noverlap.length; i++){
                System.out.println(noverlap[i]);
        }
        System.out.println();
        String[] overlap = findAllCombinedRE(p1, p2, s, true);
        for (int i=0; i<overlap.length; i++){
                System.out.println(overlap[i]);
        }
    }
}