Среди строк в алфавите из c символов пусть S имеет длину s, а T_1 ... T_k имеет среднюю длину b.S будет найден для каждой из k целевых строк.(В постановке задачи не упоминается многократный поиск данной строки; я упоминаю об этом ниже, потому что в этой парадигме моя программа работает хорошо.)
Программа использует O (s + c) время и пространство для настройки,и (если S и T_i - случайные строки) O (k * u * s / c) + O (k * b + k * b * s / c ^ u) общее время поиска, с u = 3 в программе какпоказано на рисунке.Для более длинных целей следует увеличить u и выбрать редкие, широко разделенные ключевые символы.
На шаге 1 программа создает массив L из s + TsizMax целых чисел (в программе TsizMax = допустимая длина цели)и использует его для c списков местоположений следующих вхождений символов, с заголовками списков в H [] и хвостами в T [].Это O (s + c) шаг времени и пространства.
На шаге 2 программа многократно читает и обрабатывает целевые строки.На шаге 2A выбирается u = 3 разных непростых ключевых символа (в текущей цели).Как показано, программа просто использует первые три таких символа;с чуть большим количеством работы, он мог бы вместо этого использовать самые редкие символы в цели, чтобы улучшить производительность.Обратите внимание, что он не справляется с целями, у которых менее трех таких символов.
Строка "L [T [r]] = L [g + i] = g + i;"на шаге 2A устанавливает защитную ячейку в L с надлежащим дельта-смещением, чтобы шаг 2G автоматически выполнялся в конце поиска, без необходимости дополнительного тестирования во время поиска.T [r] индексирует хвостовую ячейку списка для символа r, поэтому ячейка L [g + i] становится новым, самоссылающимся концом списка для символа r.(Этот метод позволяет циклам выполняться с минимумом тестирования посторонних условий.)
Шаг 2B устанавливает переменные a, b, c в местоположения заголовка списка и устанавливает соответствующие дельты dab, dac и dbcрасстояния между выбранными ключевыми символами в цели.
Шаг 2C проверяет, присутствуют ли ключевые символы в S. Этот шаг необходим, поскольку в противном случае цикл while на шаге 2E зависнет.Мы не хотим больше проверок внутри этих циклов while, потому что они являются внутренними циклами поиска.
Шаг 2D выполняет шаги 2E-2i до тех пор, пока var c не укажет после конца S, после чего невозможно выполнитьсделайте больше совпадений.
Шаг 2E состоит из u = 3 циклов while, которые «обеспечивают дельта-расстояния», то есть индексы сканирования a, b, c вдоль друг друга, пока они не являются шаблонами-совместимы.Циклы while довольно быстрые, каждый из которых по сути (с удаленным инструментарием ++ si) «while (v + d
На шаге 2G мы знаем, что ключевые символы u совпадают, поэтому мы проводим полное сравнение цели с точкой совпадения., с обработкой диких символов.Шаг 2H сообщает результат сравнения.Программа как дано также сообщает о несоответствиях в этом разделе;удалите это в производственном процессе.
Шаг 2I продвигает все индексы ключевых символов, поскольку ни один из индексируемых в настоящее время символов не может быть ключевой частью другого соответствия.
Вы можете запустить программу дляувидеть немного статистики по количеству операций.Например, вывод
Target 5=<de?ga>
012345678901234567890123456789012345678901
abc1efgabc2efgabcde3gabcdefg4bcdefgabc5efg
@ 17, de?ga and de3ga match
@ 24, de?ga and defg4 differ
@ 31, de?ga and defga match
Advances: 'd' 0+3 'e' 3+3 'g' 3+3 = 6+9 = 15
показывает, что шаг 2G был введен 3 раза (т. Е. Ключевые символы совпали 3 раза);полное сравнение удвоилось;шаг 2E, в то время как циклы продвинутых индексов 6 раз;шаг 2I продвинутых индексов 9 раз;было всего 15 достижений в поиске 42-символьной строки для цели degaga.
/* jiw
$Id: stringsearch.c,v 1.2 2011/08/19 08:53:44 j-waldby Exp j-waldby $
Re: Concept-code for searching a long string for short targets,
where targets may contain wildcard characters.
The user can enter any number of targets as command line parameters.
This code has 2 long strings available for testing; if the first
character of the first parameter is '1' the jay[42] string is used,
else kay[321].
Eg, for tests with *hay = jay use command like
./stringsearch 1e?g a?cd bc?e?g c?efg de?ga ddee? ddee?f
or with *hay = kay,
./stringsearch bc?e? jih? pa?j ?av??j
to exercise program.
Copyright 2011 James Waldby. Offered without warranty
under GPL v3 terms as at http://www.gnu.org/licenses/gpl.html
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
//================================================
int main(int argc, char *argv[]) {
char jay[]="abc1efgabc2efgabcde3gabcdefg4bcdefgabc5efg";
char kay[]="ludehkhtdiokihtmaihitoia1htkjkkchajajavpajkihtijkhijhipaja"
"etpajamhkajajacpajihiatokajavtoia2pkjpajjhiifakacpajjhiatkpajfojii"
"etkajamhpajajakpajihiatoiakavtoia3pakpajjhiifakacpajjhkatvpajfojii"
"ihiifojjjjhijpjkhtfdoiajadijpkoia4jihtfjavpapakjhiifjpajihiifkjach"
"ihikfkjjjjhijpjkhtfdoiajakijptoik4jihtfjakpapajjkiifjpajkhiifajkch";
char *hay = (argc>1 && argv[1][0]=='1')? jay:kay;
enum { chars=1<<CHAR_BIT, TsizMax=40, Lsiz=TsizMax+sizeof kay, L1, L2 };
int L[L2], H[chars], T[chars], g, k, par;
// Step 1. Make arrays L, H, T.
for (k=0; k<chars; ++k) H[k] = T[k] = L1; // Init H and T
for (g=0; hay[g]; ++g) { // Make linked character lists for hay.
k = hay[g]; // In same loop, could count char freqs.
if (T[k]==L1) H[k] = T[k] = g;
T[k] = L[T[k]] = g;
}
// Step 2. Read and process target strings.
for (par=1; par<argc; ++par) {
int alpha[3], at[3], a=g, b=g, c=g, da, dab, dbc, dac, i, j, r;
char * targ = argv[par];
enum { wild = '?' };
int sa=0, sb=0, sc=0, ta=0, tb=0, tc=0;
printf ("Target %d=<%s>\n", par, targ);
// Step 2A. Choose 3 non-wild characters to follow.
// As is, chooses first 3 non-wilds for a,b,c.
// Could instead choose 3 rarest characters.
for (j=0; j<3; ++j) alpha[j] = -j;
for (i=j=0; targ[i] && j<3; ++i)
if (targ[i] != wild) {
r = alpha[j] = targ[i];
if (alpha[0]==alpha[1] || alpha[1]==alpha[2]
|| alpha[0]==alpha[2]) continue;
at[j] = i;
L[T[r]] = L[g+i] = g+i;
++j;
}
if (j != 3) {
printf (" Too few target chars\n");
continue;
}
// Step 2B. Set a,b,c to head-of-list locations, set deltas.
da = at[0];
a = H[alpha[0]]; dab = at[1]-at[0];
b = H[alpha[1]]; dbc = at[2]-at[1];
c = H[alpha[2]]; dac = at[2]-at[0];
// Step 2C. See if key characters appear in haystack
if (a >= g || b >= g || c >= g) {
printf (" No match on some character\n");
continue;
}
for (g=0; hay[g]; ++g) printf ("%d", g%10);
printf ("\n%s\n", hay); // Show haystack, for user aid
// Step 2D. Search for match
while (c < g) {
// Step 2E. Enforce delta distances
while (a+dab < b) {a = L[a]; ++sa; } // Replicate these
while (b+dbc < c) {b = L[b]; ++sb; } // 3 abc lines as many
while (a+dac > c) {c = L[c]; ++sc; } // times as you like.
while (a+dab < b) {a = L[a]; ++sa; } // Replicate these
while (b+dbc < c) {b = L[b]; ++sb; } // 3 abc lines as many
while (a+dac > c) {c = L[c]; ++sc; } // times as you like.
// Step 2F. See if delta distances were met
if (a+dab==b && b+dbc==c && c<g) {
// Step 2G. Yes, so we have 3-letter-match and need to test whole match.
r = a-da;
for (k=0; targ[k]; ++k)
if ((hay[r+k] != targ[k]) && (targ[k] != wild))
break;
printf ("@ %3d, %s and ", r, targ);
for (i=0; targ[i]; ++i) putchar(hay[r++]);
// Step 2H. Report match, if found
puts (targ[k]? " differ" : " match");
// Step 2I. Advance all of a,b,c, to go on looking
a = L[a]; ++ta;
b = L[b]; ++tb;
c = L[c]; ++tc;
}
}
printf ("Advances: '%c' %d+%d '%c' %d+%d '%c' %d+%d = %d+%d = %d\n",
alpha[0], sa,ta, alpha[1], sb,tb, alpha[2], sc,tc,
sa+sb+sc, ta+tb+tc, sa+sb+sc+ta+tb+tc);
}
return 0;
}
Обратите внимание: если вам нравится этот ответ лучше, чем текущий предпочтительный ответ, снимите его и отметьте этот,:)