MergeSample.java

import java.util.ArrayList;
import java.util.Arrays;

public class MergeSample {

    public static int fPoints(String phrase, String keywords) {
        keywords = keywords.toLowerCase().trim().replaceAll(" +", " ");
        phrase = phrase.toLowerCase().trim().replaceAll(" +", " ");

        // matching all phrase
        String pattern5 = String.format("^%s$", keywords);
        // starting with phrase
        String pattern4 = String.format("^%s( |$).*", keywords);
        // ended with phrase
        String pattern3 = String.format(".* %s$", keywords);
        // has words in order
        String pattern2 = String.format("(.*)( |^)%s( |$)(.*)", keywords.replace(" ", "( | .* )"));
        // has any words in phrase
        String pattern1 = String.format(".*(( |^)%s( |$)).*", keywords.replace(" ", "( |$)|( |^)"));

        if (phrase.matches(pattern5)) {
            return 5;
        }
        else if (phrase.matches(pattern4)) {
            return 4;
        } else if (phrase.matches(pattern3)) {
            return 3;
        } else if (phrase.matches(pattern2)) {
            return 2;
        } else if (phrase.matches(pattern1)) {
            return 1;
        } else {
            return 0;
        }
    }

    public static ArrayList<String> merge(ArrayList<String> apiItems, ArrayList<String> deviceItems, String keywords) {
        // if there is no item from api, return list of item from device
        if (apiItems == null || apiItems.size() == 0) {
            return (ArrayList<String>)deviceItems.clone();
        }

        // clone api-items to result
        ArrayList<String> result = (ArrayList<String>)apiItems.clone();
        // always ignore first item of api-items, insert from second position
        int lastMergedIndex = 1;
        int lastSelectedItemIndex = 0;
        
        // travel all device items
        for (int i = 0; i < deviceItems.size(); i++) {
            String deviceItem = deviceItems.get(i);
            int deviceItemPoints = fPoints(deviceItem, keywords);
            
            // travel api-items from last checked item
            for (int j = lastMergedIndex; j < apiItems.size(); j++) {
                String apiItem = apiItems.get(j);
                int apiItemsPoints = fPoints(apiItem, keywords);

                // if device-item is better than api-item, insert device-item to result at api-item position
                if (deviceItemPoints > apiItemsPoints) {
                    lastMergedIndex = j + 1;
                    lastSelectedItemIndex = i;
                    result.add(j, deviceItem);
                    break;
                }
            }
        }
        
        // merge the rest of device-items to result
        if (lastSelectedItemIndex < deviceItems.size() - 1) {
            result.addAll(deviceItems.subList(lastSelectedItemIndex + 1, deviceItems.size()));
        }
        return result;
    }

    public static void main(String[] args) {
        ArrayList<String> Apis = new ArrayList<String>(Arrays.asList("cơn mưa đêm", "cơn mưa chiều", "mùa mưa", "trơi mưa quá", "con mưa ngang qua"));
        ArrayList<String> Devides = new ArrayList<String>(Arrays.asList("qua cơn mưa", "cơn mưa", "cơn trời mưa", "hết mưa", "mưa rồi", "sao trời mưa vậy"));
        ArrayList<String> re = merge(Apis, Devides, "cơn mưa");
        for (int i = 0; i < re.size(); i++) System.out.println(re.get(i));
    }
}