Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.91
Андрeй
Сообщений: n/a
#1

Поиск строк - C++

23.08.2007, 12:06. Просмотров 2832. Ответов 1
Метки нет (Все метки)

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

Вот что с сделал с БМ, недостаток в том, что если искомая строка входит в буфер(BufferRead) не целиком, тогда она оказывается не найденой программой.

Как можно дописать это?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
using namespace std;
#include <stdio.h>     /* для printf */
#include <stdlib.h>    /* для exit */
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include<string.h>
#include<fcntl.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
int ASIZE=255,XSIZE;
/* Preprocessing of the Bad Character function shift */
void PRE_BC( char *x, int m, int bm_bc[] ) {
   int a, j;
   for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m; 
   for ( j=0; j < m-1;  j++ ) bm_bc[ (unsigned char)x[ j ] ] = m - j - 1; 
  }
 /* Preprocessing of the Good Suffix function shift  */
void PRE_GS( char *x, int m,  int bm_gs[] ) {
   int i, j, p, f[XSIZE];
   memset( bm_gs, 0, ( m + 1 ) * sizeof( int ) );
   f[ m ] = j = m + 1; 
   for (i=m; i > 0; i-- ) {
      while ( j <= m && x[ i - 1 ] != x[ j - 1 ] ) {
        if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = j - i;
       j = f[ j ];
     }
     f[ i - 1 ] = --j; 
   }
   p=f[ 0 ]; 
   for ( j=0; j <= m; ++j ) {
      if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = p; 
     if ( j == p ) p = f[ p ]; 
   }
}
 
/* Boyer-Moore string matching algorithm */
void BM( char *x, char *y, int m )
{
    int fd,rd,bufferSize=128,i, j, bm_gs[XSIZE], bm_bc[ASIZE];
    char bufferRead[bufferSize];
    if((fd=open(y,O_RDONLY)) == -1)
    {
        fprintf(stderr,"Open failed:%s (errno=%d)\n",strerror(errno),errno);
        exit(EXIT_FAILURE);
    }
  /* Preprocessing */
  PRE_GS( x, m, bm_gs );
  PRE_BC( x, m, bm_bc );
int n,count=1;
while ((rd=read(fd,bufferRead,bufferSize))>0)
{i=0;
//
y=bufferRead;
n=strlen(bufferRead);
  while ( i <= n-m )
   {//from file
    for ( j=m-1; j >= 0 && x[ j ] == y[ i+j ]; --j );
    if ( j < 0 )
    {
      printf("%d \n",count*bufferSize+i);
      i += bm_gs[ j+1 ];
    }
    else i += MAX(( bm_gs[ j+1 ]), ( bm_bc[ (unsigned char)y[ i+j ] ] - m + j + 1 ) );
   }
count ++;
}
}
 
int main(void)
{
char ToFindIn[]="Java";
XSIZE=strlen(ToFindIn);
BM(ToFindIn,"/home/andrey_polyakov/1.html",XSIZE);
printf("finished\n");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2007, 12:06     Поиск строк
Посмотрите здесь:

Поиск строк - C++
Мне нужно найти в строке символ &quot;,&quot; и заменить ее. Данная программа демонстрирует нахождение одной запятой #include&lt;iostream&gt; ...

Поиск строк по образцу - C++
Если в командной строке заданы опции -x -n &lt;образец&gt;, то необходимо распечатать те строки введенного текста с их номерами, в которых не...

Поиск в массиве строк - C++
Добрый день Возник глупый вопрос. Пытаюсь сделать поис в строковом массиве не как не получается подскажите что не такк. Сам массив...

Поиск строк в файле по маске - C++
Программа осуществляет в файле поиск строк, отвечающих заданной маске. В маску могут входить символ «?» (любой печатный символ или пусто)....

Обработка строк и поиск подстроки - C++
Нужно исправить ошибки, не знаю что это и как исправить 4 шт) недопустимо, левый операнд имеет тип &quot;unsigned int (__thiscall...

Поиск повторяющихся строк в файле - C++
Нужна рекомендация! Есть сгенерированные цепочки (строки) которые записаны и в файл, и естественно выводятся с него. Нужно сделать...

Поиск строк с нулевыми элементами - C++
Всем привет народ,помогите пожалуйста решить такую задачу:(: Для матрицы А вывести те строки, в которых есть нулевые элементы, или...

Поиск строк, начинающихся с пробела. - C++
Нужно посчитать количество строк в файле, начнающихся с пробела и вывести количество в выходной файл. Выдает ошибку=( Почему? ...

Массив строк, не правильный поиск - C++
Вводим имя, инструмент, год рождения, время обучения. Хочу вывести имя ученика играюшего на скрипке, но он упорно выводит имена всех....

Поиск определенных строк в текстовом файле - C++
Здравствуйте. Есть файл &quot;file.txt&quot; в котором есть строки: Bread: 3 Milk: 1 Chicken: 4 Juice: 3 Potatoes: 2 Tomatoes: 1 ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
WADDICK
Сообщений: n/a
24.08.2007, 12:30     Поиск строк #2
Можно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
DWORD FindDataInMem(LPBYTE Source,DWORD SourceSize,LPBYTE FindData,DWORD FindDataSize,DWORD StartPointer=0)
 {
     DWORD j=0;
     __asm
     {
         //Главный цикл
         mov ecx,StartPointer
main_cycle:
         //Проверка условия главного цикла
         cmp SourceSize,eцx
         jl func_end
         //Если Source[i]==FindData[0]
         mov al,byte ptr[Source+ecx]
         cmp al,byte ptr[FindData]
   //Если al==byte ptr[FindData]
         je end_main_cycle
         mov ebx,FindDataSize
cycle2_begin:
         //if(Source[i+j]!=FindData[j])
         mov eax,ecx
         add eax,ebx
         mov al,byte ptr[Source+eax]
         cmp al,byte ptr[FindData+ebx]
         jne end_main_cycle
         loop cycle2_begin
         push ecx;
 
         //Инкремент главного цикла и повтор
end_main_cycle:
         inc ecx
         jmp main_cycle
func_end:
         ret;
 
     }
 }
Или так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    wcout.imbue(std::locale("Russian_russia.OCP"));
             string s1;
    wcout<<L"Введите строку с пробелами"<<endl;
             getline(cin,s1, '\n');
    string word("test");
    string::size_type pos = 0,prev_pos = 0;
    vector<string> vec;
    while((pos = s1.find_first_of(' ',pos))
        != string::npos){
                 vec.push_back(s1.substr(prev_pos,
          pos - prev_pos));
       prev_pos = ++pos;
    }
    vec.push_back(s1.substr(prev_pos,
        pos - prev_pos));
    for(int i = 0;i<vec.size();++i)
        cout<<vec[i]<<' ';
    cout<<endl;
    int count = 0;
    for(int i = 0;i<vec.size();++i){
        if(vec[i] == word){
        wcout<<L"Искомое слово находится в "<<
                 i<<L" - й позиции"<<endl;
                          ++count;
        }
    }
    if(count == 0)
      wcout<<L"Искомое слово не найдено"<<endl;
    return 0;
}
Yandex
Объявления
24.08.2007, 12:30     Поиск строк
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru