Соответствие шаблону строки, суффиксный массив может решить эту проблему или иметь больше решений?

У меня есть строка, которая генерируется случайным образом с помощью специальных символов (B,C,D,F,X,Z), например, чтобы создать следующий список строк:

B D Z Z Z C D C Z
B D C
B Z Z Z D X 
D B Z F
Z B D C C Z
B D C F Z
..........

у меня также есть список шаблонов, то есть для сопоставления сгенерированной строки, возврата наилучшего шаблона и извлечения некоторой строки из строки.

струнный узор

B D C [D must appear before the C >> DC]
B C F
B D C F
B X [if string have X,must be matched.]
.......

например,

B D Z Z Z C D C Z,который имеет B а также DC, так что может соответствовать B D C

D B Z C F,который имеет B а также C а также F, так что может соответствовать B C F

D B Z D F,который имеет B а также F, так что может соответствовать B F

.......

теперь я просто думаю о suffix array,

1. сначала преобразовать строку в суффикс массива объекта.

2. Зафиксируйте каждый шаблон, чтобы найти, какой суффиксный массив может быть сопоставлен.

3.Сравните все подходящие шаблоны и получите лучший шаблон.

var suffix_array=Convert a string to suffix array.
var list=new List();
for (int i=0;i<pattern length;i++){
    if (suffix_array.match(pattern))
        list.Add(pattern);
}
var max=list[0];
for (int i=1;i<list.length;i++){
{
   if (list[i]>max)
      max=list[i];
      Write(list[i]);
}

я просто думаю, что этот метод сложный, что нужно построить дерево для шаблона, и принять его в соответствии с суффиксом array.who есть идеи?

==================== обновление

Теперь я получаю лучшее решение, я создаю новый класс, который имеет свойство B,C,D,X..., которое является свойством array type.each, сохраняя позицию, которая появляется в строке. Теперь, если B не появляется в строке, мы можем немедленно завершить эту обработку. мы также можем получить все позиции C и D, а затем сравнить их, могут ли они появиться последовательно (DC,DCC,CCC....)

2 ответа

var suffix_array=Convert a string to suffix array.
var best=(worst value - presumably zero - pattern);
for (int i=0;i<pattern list array length;i++){
  if (suffix_array.match(pattern[i])){
    if(pattern[i]>best){
      best=pattern[i];
    }
    (add pattern[i] to list here if you still want a list of all matches)
  }
}
write best;

Грубо говоря, в любом случае, если я понимаю, что вы ищете, это небольшое улучшение, хотя я уверен, что может быть лучшее решение.

Я не уверен, какой язык программирования вы используете; Вы проверили его возможности с помощью регулярных выражений? Если вы не знакомы с ними, вы должны нажать Google.

Другие вопросы по тегам