Соответствие шаблону строки, суффиксный массив может решить эту проблему или иметь больше решений?
У меня есть строка, которая генерируется случайным образом с помощью специальных символов (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.