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

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

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

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

25.08.2011, 20:21. Просмотров 2553. Ответов 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;
}
Медленно, кто-нибудь может ускорить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2011, 20:21     Молниеносное нахождение подстрок
Посмотрите здесь:

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
26.08.2011, 15:16     Молниеносное нахождение подстрок #41
Может быть, это поможет?
Напишите свои аналоги функций strlen(), strcpy(), strcmp() и сравните с библиотечными.
Там строка проматывается кусками по несколько байт.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.08.2011, 15:30     Молниеносное нахождение подстрок #42
Цитата Сообщение от #pragma Посмотреть сообщение
Там строка проматывается кусками по несколько байт.
Выглядит как будто бы Вы предлагаете использовать брутфорс. Я думаю, здесь все же немного другой случай.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 16:46     Молниеносное нахождение подстрок #43
AvengerAlive, ваша задача с какого сайта?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.08.2011, 02:40     Молниеносное нахождение подстрок
Еще ссылки по теме:

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

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

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

Реализация алгоритма поиска подстрок чжу такаоки на c++ - C++
У кого нибудь есть алгоритм поиска подстрок чжу такаоки на c++?)

Реализовать поиск подстрок с помощью недетерминированного конечного автомата - C++
Всем привет!Сразу к сути задачи.Необходимо реализовать поиск подстрок с помощью недетерминированного конечного автомата. Вообще не...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.08.2011, 02:40     Молниеносное нахождение подстрок #44
AvengerAlive,
ссылку на задачу можете дать?
Yandex
Объявления
27.08.2011, 02:40     Молниеносное нахождение подстрок
Ответ Создать тему
Опции темы

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