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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.60
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

Молниеносное нахождение подстрок - C++

25.08.2011, 20:21. Просмотров 2649. Ответов 43
Метки нет (Все метки)

Воодится число тестов. Далее каждый тест содержит 2 строки. Подстроку и текст. Надо найти количество подстрок в тексте. Количество тестов неизвестно, но много. Длина подстроки 10000, а текста 1000000.
Вот мой код:
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
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
string str1;
string str2;
string str;
int i,n,m,q=0,t,k,a;
int *mas;
cin >> t;
while (t--)
{
 cin >> str2;
 cin >> str1;  
 n=str1.length();
 m=str2.length();
 mas=(int*)malloc((n+m+1)*sizeof(int));
 str=str2+'#'+str1; mas[0]=0;
 a=0; k=0; q=0;
 for(i=1; i<n+m+1; i++)
  {         
   while((k>0) && (str[k]!=str[i])) k=mas[k-1];
   if (str[k]==str[i]) k++;
   if (k==m) q++;
   mas[i]=k;
  }
 cout << q << endl;
}
return 0;
}
Медленно, кто-нибудь может ускорить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2011, 20:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Молниеносное нахождение подстрок (C++):

Поиск подстрок - C++
Задание подсчитать все подстроки с использованием функции strstr(). Делаю так: int NumSubStr(char *str1, char *str2){ int result...

Количество подстрок в строке - C++
Нужно что-бы пользователь ввел 2 строки и ему вывело сообщение о том, сколько раз встречается строка 2 в первой строке. Как это сделать без...

Удаление подстрок из строки - C++
Помогите, пожалуйста, с реализацией функции. Есть строка str типа string и строка it типа char. Нужно из str удалить все it. Например, ...

Подсчёт количества подстрок - C++
Посмотрите пожалуйста нормально ли написана функция, которая считает количество подстрок? int SearchSubString(char *s1,char *s2){ ...

Удаление всех подстрок из строки - C++
Здравствуйте. После выполнения моей программы у меня выдает вот такую ошибку #include &lt;iostream&gt; #include &lt;string&gt; ...

Подсчитать количество подстрок в текстовом файле - C++
Помогите написать программу которая может подсчитать сколько раз подстрока встречается в текстовом файле.

43
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
25.08.2011, 22:47 #31
Цитата Сообщение от easybudda Посмотреть сообщение
без понятия, что там со скоростью...
Алгоритм как у xAtom и опять здесь надо поменять
C++
1
ptr = strstr(ptr + len, sub)
на
C++
1
ptr = strstr(ptr+1, sub)
и опять скорость хромать в олимпиадной задаче будет

Добавлено через 3 минуты
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
AvengerAlive, попробуйте алгоритм Рабина-Карпа...
Мне этот алгоритм тоже по душе, но все же не универсальный алгоритм и все зависит еще и от способа хэширования.

Добавлено через 42 минуты
А за тему, AvengerAlive, спасибо, очень интересная тема, но увы, универсальных методов нет, все разваливается на ситуации, в которых лучше применять тот или иной метод.
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
26.08.2011, 09:58  [ТС] #32
Olga_, Мне тут посоветовали посимвольно считывать и обрабатывать символы, в моей программе надо просто как-то это добавить, но дело в том что размеры слов я не знаю, и как понять что я считываю и сколько считываю? Посимвольно так он все 10000 тестов как 1 посчитает? Пробовал с \n \0 если встретится вырубить, но бес толку. Как это сделать?

Добавлено через 25 минут
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 <iostream>
#include <cstring>
using namespace std;
 
int main()
{
 char str[1010002];
 int i,m,q=0,t,k,a,e;
 int *mas;
 cin >> t;
 mas=(int*)malloc(1010002*sizeof(int));
 while (t--)
  {
   mas[0]=0;
   a=0; k=0; q=0; i=0; e=0; m=10002;
   while (true)
    {       
     cin >> str[i]; 
     if (str[i]=='\0') 
      { 
       if (e) break; 
       if (!e) 
        {
         e=1; 
         str[i]='#';
         m=i; 
        } 
      }
     while((k>0) && (str[k]!=str[i])) k=mas[k-1];
     if (str[k]==str[i]) k++;
     if (k==m) q++;
     mas[i]=k;
     i++;
    }
   cout << q << endl;
  }
 return 0;
}
Добавлено через 55 секунд
Вот то посимвольное, но оно не работает. Мб посимвольно если исправить + scanf'ом быстрее будетю
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
26.08.2011, 11:09 #33
AvengerAlive, вы хотите разделять тексты? Если правильно поняла вас, используйте флаг EOF после ввода очередной пары текстов (текст и искомый подтекст), он вводится как ctrl+z или ctrl+d в зависимости от операционной системы. Тогда проверка будет
C++
1
if (str[i] == EOF)
Еще обратите внимание, что
C++
1
 cin >> str[i];
неправильно, вы так все пробелы пропускаете. Тогда уж
C++
1
str[i] = cin.get();
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
26.08.2011, 11:32  [ТС] #34
Там пробелов нет. Просто слово aza и длинное azabbansdbaazazaaaazaaaaajhdbabzabahbza и всё. Входные данные имеют такой вид

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Как тут EOF делать? Это же уже вроде самими создателями задачки написано.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
26.08.2011, 11:51 #35
Считывайте cin.get() и проверяйте на '\n'
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
26.08.2011, 13:10  [ТС] #36
Считал, всё выдаёт нормально, но теперь почему-то префикс функция некорректно работает.

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
#include <iostream>
#include <cstring>
using namespace std;
 
int main()
{
 char str[1010002];
 char ch;
 int i,m,q=0,t,k,a,e;
 int *mas;
 cin >> t;
 cin.get(ch);
 mas=(int*)malloc(1010002*sizeof(int));
 while (t--)
  {
   mas[0]=0;
   a=0; k=0; q=0; i=1; e=0; m=10002;
   cin.get(str[0]);
   cout << str[0];
   while (true)
    {       
     cin.get(str[i]);    
     if (str[i]=='\n') 
      { 
       if (e) break; 
       else if (!e) 
        {
         e=1; 
         str[i]='#';
         m=i-1; 
        } 
      }
     cout << str[i];
     while((k>0) && (str[k]!=str[i])) k=mas[k-1];
     if (str[k]==str[i]) k++;
     if (k==m) q++;
     mas[i]=k;
     i++;
    }
   cout << q << endl;
  }
 return 0;
}
Тесты:
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Надо 1 3 0, а выдаёт 1 3 1.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.08.2011, 13:13 #37
Писал КМП когда-то
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
#include <iostream>
#include <cstring>
void prefix(char * str, int * arr) {
    *arr = 0;
    for (int i = 1; str[i]; ++i)
    {
        int j = arr[i - 1];
        while ( j && str[i] != str[j] )
            j = arr[j - 1];
        arr[i] = j + (str[i] == str[j]);
    }
}
char a[99999], b[99999];
int pref[99999];
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::cin >> a >> b;
    int i = strlen(b), n = i;
    b[i] = '#';
    for(int j = 0; b[++i] = a[j++]; );
    prefix(b, pref);
    for (int i = n + 1; b[i]; ++i)
        if (pref[i] == n )
            std::cout << i - 2 * n << ' ';  
}
Только у меня там выводятся вхождения, а вам нужно просто увеличивать счетчик.
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
26.08.2011, 13:32  [ТС] #38
diagon, спасибо, но очень жаль, медленно, те же 3 теста не проходят. Тут фишка в том что префикс это онлайновая функция. Надо быстро каждый символ считывать и обрабатывать, не делать лишние N+M операций на считывание всей строки...

Добавлено через 3 минуты
НАШЁЛ ОШИБКУ! Всё работает. Но Olga_, этот метод оказывается ещё медленнее работает, уже 5 тестов с TL. Что делать?
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.08.2011, 13:34 #39
Цитата Сообщение от AvengerAlive Посмотреть сообщение
diagon, спасибо, но очень жаль, медленно, те же 3 теста не проходят. Тут фишка в том что префикс это онлайновая функция. Надо быстро каждый символ считывать и обрабатывать, не делать лишние N+M операций на считывание всей строки...
Посимвольно еще неэффективнее должно быть.
Этот алгоритм побыстрее будет.
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
26.08.2011, 14:11  [ТС] #40
diagon, читал, всё ранво медленно, даже scanf медленно... не знаю уже что делать...
0
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
26.08.2011, 15:16 #41
Может быть, это поможет?
Напишите свои аналоги функций strlen(), strcpy(), strcmp() и сравните с библиотечными.
Там строка проматывается кусками по несколько байт.
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.08.2011, 15:30 #42
Цитата Сообщение от #pragma Посмотреть сообщение
Там строка проматывается кусками по несколько байт.
Выглядит как будто бы Вы предлагаете использовать брутфорс. Я думаю, здесь все же немного другой случай.
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 16:46 #43
AvengerAlive, ваша задача с какого сайта?
0
valeriikozlov
Эксперт С++
4671 / 2497 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.08.2011, 02:40 #44
AvengerAlive,
ссылку на задачу можете дать?
0
27.08.2011, 02:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2011, 02:40
Привет! Вот еще темы с ответами:

Поиск подстрок в строках и вывод в файл - C++
Дан файл, html код страницы, в котором есть повторения типа &quot;email: password&quot;, например: lal@mail.ru: TXGgQ32Bh8J7PQn6J ...

Свертка повторяющихся подстрок по следующим правилам - C++
Помогите, не могу понять задание. В заданной строке символов выполнить свертку повторяющихся подстрок по следующим правилам: а)...

Найти количество вхождений подстрок в строку - C++
Собственно, в input.txt лежит строка размером до 250 символов, в output.txt нужно найти количество вхождений в нее подстрок, а именно...

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


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

Или воспользуйтесь поиском по форуму:
44
Ответ Создать тему
Опции темы

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