Поиск строки в файле (быстрее, ещё быстрее :))

galileopro
str = "aaab";
substr = "aab";

 

Код (Text):

1. var Str, subStr:String;
2.     i, j, subStrLen : integer;
3. begin
4.  Str := 'aaab';
5.  subStr := 'aab';
6.  i := 1;
7.  j := 1;
8.  subStrLen := length(subStr);
9. repeat
10. if j > 1 then begin
11.     if (subStr[j] = Str[i]) then inc(j)
12.                             else j := 1;
13.               end
14.               else begin
15. if (subStr[j] = Str[i])and(subStr[subStrLen] = Str[i + subStrLen - j]) then inc(j)
16.                              else j := 1;
17.               end;
18. inc(i);
19. until (j = subStrLen + 1) or ( i > length(Str));
20. writeln( 'Index of SubString: ', i - j + 1 );

 

galileopro
Ваш алгоритм не верен. Он не учитывает возможности нахождения в нескольких состояниях. Пример привелgreen

Конечно можно построить DFA. Но это только замедлит поиск у него полно своих проблем.


PS. Занимался на досуге оптимизацией конечных автоматов. Пришел к выводу что можно заточить под определенные классы регулярных выражений.

 

Pavia, а сможете привести пример, на котором упадет код из 62 поста? Ради интереса и понимания особых ситуаций.

 

galileopro
Ты его вначале сам погоня. Выход из цикла не определен.

Ну добавил ты проверку на последний символ а на промежуточные?
Str := 'aaaabb';
subStr := 'aaabb';

Код (Text):

1. if (subStr[j] = Str[i])and(subStr[subStrLen] = Str[i + subStrLen - j]) then inc(j)
2.                              else j := 1;

тут не обязательно 1 из за повторяющихся символов она может почти любым.

За O(n) можно сделать. Но размер кэш ограничен отсюда имеем ограненный проигрыш из-за кэш промохов.
http://algolist.manual.ru/search/esearch/aut.php
http://algolist.manual.ru/search/esearch/

 

Так посередине все нормально. Оно посчитало все Ок для

Я проверяю 1 символ искомой подстроки и последний. Если они совпали, то я делаю inc(j) и дальше в эту ветку оно уже не зайдет. Оно будет проверять, фактически, символы между 1 и последним. Там уже без вариантов: если хоть один не совпал, то j:=1. Я погонял, пока оно не свалилось. И, кстати, про кеширование. Как раз для этой задачи очень подходит

Код (Text):

1. PREFETCHT0 byte ptr [eax]

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

 

galileopro

7 позиция это OK? Должна быть 2.

 

Можно переделать этот алгоритм так чтобы находил правильно. Но тогшда там в худшем случае далеко не линейное время будет, а что-то вроде n*m. Так как вот в таких ситуациях прийдется заново начинать просматривать со 2 символа, с 3-го и так пока нам не встретится буковка, отличная от a, тогда уже можно двигаться дальше. Спасибо за пример.