Максимальное совпадение для строки

Question

Я пытаюсь написать метод, который вернет мне код, соответствующий банковскому продукту, который мне нужно передать веб-службе. У меня есть массив подходящих универсальных типов продуктов, и входными данными будет строка, которая будет специфическим типом любого из универсальных типов в массиве. Позвольте мне объяснить это с помощью кода, который у меня уже есть:

public static void main(String[] args) 
{
   String[] names = { "Checking", "Savings", "DEMAT", "DEMAT Savings", "Interest Checking" };
   String input = "Employee Checking";
   int min = Integer.MAX_VALUE;
   String maxMatch = null;
   for(String name : names) 
   {
      int i = input.indexOf(name);
      if(i > -1 && i < min) 
      {
         min = i;
         maxMatch = name;
      }
   }
   if(null != maxMatch)
   {
      System.out.println("Maximum match for " + input + " found at " + maxMatch);
   }
}

Приведенный выше фрагмент пытается выполнить максимальное совпадение для ввода. Таким образом, если в качестве входных данных выбрано «Проверка интересов сотрудников», я получаю совпадение на «Проверка процентов», а не просто «Проверка».

Что я хочу знать, так это то, есть ли какой-либо способ оптимизировать этот фрагмент кода или есть случаи, когда этот код не будет работать?

Answer 1

Если вы сохраняете отсортированный массив по длине строки, вы можете быть уверены, что первое совпадение даст максимальное совпадение

import java.util.Arrays;
import java.util.Comparator;

public class MaxIndex {

private static String[] names = { "Checking", "Savings", "DEMAT", "DEMAT Savings",
        "Interest Checking","Savings Interest Checking","My Employee Savings Interest Checking" };

public static void main(String[] args) {

    Arrays.sort(names, new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
            Integer L1 = o1.length();
            return L1.compareTo(o2.length())*-1;
        }
    });

    findMaxMatch("Employee Checking");
    findMaxMatch("Employee Savings");
    findMaxMatch("Employee Interest Checking");
    findMaxMatch("Employee Savings Interest Checking");
    findMaxMatch("My Employee Savings Interest Checking");
    findMaxMatch("Employee Current");
}

private static void findMaxMatch(String input) {
    String maxMatch = maxMatch(input);
    if (null != maxMatch) {
        System.out.println("Maximum match for '" + input + "' found at '"
                + maxMatch+"'");
    }else{
        System.out.println("No match for '"+input+"'");
    }
}

private static String maxMatch(String input) {
    for (String name : names) {
        int i = input.indexOf(name);
        if (i > -1) {
            return name;
        }
    }
    return null;
}

}

выход

Maximum match for 'Employee Checking' found at 'Checking'
Maximum match for 'Employee Savings' found at 'Savings'
Maximum match for 'Employee Interest Checking' found at 'Interest Checking'
Maximum match for 'Employee Savings Interest Checking' found at 'Savings Interest Checking'
Maximum match for 'My Employee Savings Interest Checking' found at 'My Employee Savings Interest Checking'
No match for 'Employee Current'

Answer 2

Если я правильно понимаю ваш вопрос, вы хотите найти самое длинное совпадение в случае нескольких совпадений.Один из способов сделать это - отсортировать ваши «имена» в порядке убывания (исходя из их длины) и остановиться на первом совпадении.

Это можно сделать с помощью SortedMap., в котором вы бы указали длину каждого «имени» из «имен» в качестве его ключа.

Например, выполнив что-то вроде этого:

SortedMap<Integer,String> map = new TreeMap<Integer, String>( new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        return -o1.compareTo(o2);
    }
});
for ( final String name: names ) {
    map.put(name.length(),name);
}

Затем выитерация и остановка, как только вы найдете первое совпадение.

Это своего рода "перебор", но это работает.

Answer 3

Если я правильно вас понимаю, найденная строка всегда может быть подстрокой запроса?

Используйте contains(), чтобы найти подстроку, и, если она найдена, сохраните ее, если она самая длинная.

public static void main(String[] args) 
{
    String[] names = {"Checking", "Savings", "DEMAT", "DEMAT Savings", "Interest Checking"};
    String input = "Employee Interest Checking";
    int min = Integer.MIN_VALUE;
    String maxMatch = null;
    for (String name : names)
    {
        boolean has = input.contains(name);
        if (has && min < name.length())
        {
            min = name.length();
            maxMatch = name;
        }
    }
    if (null != maxMatch)
    {
        System.out.println("Maximum match for " + input + " found at " + maxMatch);
    }
}

и так же, как сказал user988052; если вы упорядочите массив правильно, вы можете остановиться на первом совпадении, чтобы вам больше не пришлось искать, и вы можете исключить min.

Упорядочение массива по убыванию по длине:

    Arrays.sort(names, new Comparator<String>()
    {
        public int compare(String o1, String o2)
        {
            int d = o2.length() - o1.length();
            return d != 0? d : ((Comparable<String>)o1).compareTo(o2);
        }
    });

Answer 4

используйте это для нахождения последней позиции

names.lastIndexOf(input)

на основе позиции массива, получите значение

Answer 5

Это не удастся, если максимальное совпадение не было в первой части строки.Например, если вы вводите Interest Checking For Employees, то оно будет соответствовать Checking вместо Interest Checking.Должно ли максимальное совпадение найти аккаунт с наиболее последовательными совпадающими символами?Или просто совпадение, наиболее близкое к концу ввода?