Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.60
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
#1

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

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

Воодится число тестов. Далее каждый тест содержит 2 строки. Подстроку и текст. Надо найти количество подстрок в тексте. Количество тестов неизвестно, но много. Длина подстроки 10000, а текста 1000000.
http://www.cyberforum.ru/cpp-beginners/thread630141.html
Вот мой код:
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++):

вырезки подстрок
написал вот такой код #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...

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

Замена подстрок в строке
Кто знает, как в данной строке заменить все подстроки &quot;123&quot; на &quot;456&quot;?

Подсчёт количества подстрок
Посмотрите пожалуйста нормально ли написана функция, которая считает количество...

Поиск и вывод подстрок
злорадствуйте подскажите пожалуйста немного запутался как вывести через find...

43
Сыроежка
Заблокирован
25.08.2011, 20:31 #2
У вас в самом начале программы выделяется память неизвестного размера, так как переменные n и m не имеют начальных значений. За счет этого у вас медленно и работает, так как программа имеет неопределенное поведение.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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));

Извините, я ошибся. У вас в цикле выдяляется память, которая не удаляется. То есть смысл вашей программы совершенно не понятен.
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 20:39  [ТС] #3
И как его задать? str1[1000001] ошибка компилляции...
0
Сыроежка
Заблокирован
25.08.2011, 20:47 #4
Цитата Сообщение от AvengerAlive Посмотреть сообщение
И как его задать? str1[1000001] ошибка компилляции...
Во-первых, если вы работаете в С++, то лучше использовать оператор new вместо функции malloc. Во-вторых, я вообще не понял, чего вы добиваетесь своей программой. Вы ввели два слова, а дальше что вы с ними собираетесь делать?

Добавлено через 5 минут
Потом я не вижу никакого смысла в этом куске кода

C++
1
2
3
4
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];
Вы задаете начальное значение для переменной 'k' равное 0, а затем у вас идет цикл while с условием k > 0, но это условие никогда не будет выполняться!

То есть вы вообще что=-то непонятное написали.
0
ValeryLaptev
Эксперт С++
1049 / 828 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
25.08.2011, 20:48 #5
AvengerAlive, давайте проясним задачу. Итак, сначала вводится N. Далее N раз по две строки. Первая строка - что ищем, вторая строка - где ищем.
Пробелы есть в строках?
Что ищем, может состоять из одного символа?
А может быть так, что размер что ищем, и размер, где ищем - совпадают?
А может быть что ищем больше, чем, где ищем?

А могут ли быть одинаковые буквы в что ищем? А все одинаковые?
А то же самое - в где ищем?

Задача случайно не олимпиадная?
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 20:49  [ТС] #6
Цитата Сообщение от Сыроежка Посмотреть сообщение
Потом я не вижу никакого смысла в этом куске кода
Код C++
1
2
3
4
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];
Это префикс функция.

Цитата Сообщение от Сыроежка Посмотреть сообщение
Вы ввели два слова, а дальше что вы с ними собираетесь делать?

Надо количество вхождений найти.
Программа работает только медленно. Последние 3 теста там видно по 1000000 всё, вот и TL.
0
Сыроежка
Заблокирован
25.08.2011, 20:52 #7
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Это префикс функция.
Я не знаю, что такое "префикс-функция". Вы С++ не знаете, а пытаетесь использовать средства, которые в текущий до сегодняшнего дня стандарт не входят.

Для поиска вхождений одной строки в другую есть функция-член класса string find.

Кроме того совершенно не понятно, что означает следующая строчка вашего кода

C++
1
str=str2+'#'+str1;
Создается впечатлдение, что вы сами не понимаете, что вы делаете в своей программе.
0
diagon
25.08.2011, 20:52
  #8

Не по теме:

Цитата Сообщение от Сыроежка Посмотреть сообщение
Я не знаю, что такое "префикс-функция". Вы С++ не знаете, а пытаетесь использовать средства, которые в текущий до сегодняшнего дня стандарт не входят.
Да, жаль что КМП не входит в стандарт с++.

0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 20:57  [ТС] #9
ValeryLaptev, нет всё проще. просто слово дано и слово подлинее.

Сыроежка, то что ты говоришь медленно работает. Наивный алгоритм намного медленнее чем префикс функция. У моего сложность O(n), а у стандарта O(n+m)
0
Сыроежка
Заблокирован
25.08.2011, 21:01 #10
Цитата Сообщение от AvengerAlive Посмотреть сообщение
ValeryLaptev, нет всё проще. просто слово дано и слово подлинее.

Сыроежка, то что ты говоришь медленно работает. Наивный алгоритм намного медленнее чем префикс функция. У моего сложность O(n), а у стандарта O(n+m)
Ничего не понял! Ваш код - это образец того, как не следует писать программы! То есть для постороннего человепка ваш код совершенно не понятен. Вам бы вместо того, чтобы рассуждать о какой-то там сложности, следовало бы научиться сначала писать элементарные конструкции на С++.
2
xAtom
917 / 742 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
25.08.2011, 21:02 #11
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Медленно, кто-нибудь может ускорить?
Вообще для скорости нужно использовать стандартные строковые функции string.h они написаны на asm. Вот пример подсчёт кол-ва подстрок, быстрее не напишешь.
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 <stdio.h>
#include <string.h>
 
int  substr_len(const char* str, const char* sub) {
    int len  = 0;
    int size = strlen(sub);
    while((str = strstr(str, sub))) { 
         len++;
         str += size;
    }
    return len;
}
 
int  main(void) {
           char str[255], sub[32];
 
           printf("in text:");
           gets(str);
           printf("in sub:");
           scanf("%s", sub);
    
           printf("sub length = %d\n", substr_len(str, sub) );
  
    getchar();
    return 0;
}
С кучами сам разберись открой любой учебник для начинающих и всё.
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:03  [ТС] #12
Сыроежка, Ну что тебе НЕ ПОНЯТНО? Вот прочитай поймёшь как это работает.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.08.2011, 21:04 #13
Цитата Сообщение от xAtom Посмотреть сообщение
Вообще для скорости нужно использовать стандартные строковые функции string.h они написаны на asm. Вот пример подсчёт кол-ва подстрок, быстрее не напишешь.
Я тоже так думал =)
Вот
Вот код
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstring>
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    char a[999999], b[999999], *p = a;
    std::cin.getline(a, 999999);
    std::cin.getline(b, 999999);
    for (; p = strstr(p, b) ; *p++ = 0)
        std::cout << p - a << ' ';
}
Не проходит по времени. КМП там же менее чем за 0.1 секунду справляется.
0
Сыроежка
Заблокирован
25.08.2011, 21:07 #14
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Сыроежка, Ну что тебе НЕ ПОНЯТНО? Вот прочитай поймёшь как это работает.
Причем здесь ваши ссылки на что-то? Я говорю про ваш код! Код совершенно некорректный и непонятно, что он делает. Между вашим кодом и содержанием вашей ссылки может быть большая разница!

Добавлено через 2 минуты
Автор темы использует С++, а не С. Это, во-первых, А, во-вторых, совершенно не понятно, почему нельзя использовать функцию-чден класса find, как я уже указал? Между прочим она также обычно основана на стандартных функциях С из библиотеки <cstring>.
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:07  [ТС] #15
xAtom, откомпиллируй, проверь... Он на тест
ababa
aba
Выдаёт ответ 1
На тест
azabbazazabbaza
aza
выдаёт 3
а на azabbazazabbazazabbazazazabb
ответ вообще 5. Не работает...
0
Сыроежка
Заблокирован
25.08.2011, 21:09 #16
Цитата Сообщение от diagon Посмотреть сообщение
Я тоже так думал =)
Вот
Вот код
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstring>
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    char a[999999], b[999999], *p = a;
    std::cin.getline(a, 999999);
    std::cin.getline(b, 999999);
    for (; p = strstr(p, b) ; *p++ = 0)
        std::cout << p - a << ' ';
}
Не проходит по времени. КМП там же менее чем за 0.1 секунду справляется.
Наверное очевидно потому, что вместо вызовов функций используются встроенная функция.
0
-=ЮрА=-
Заблокирован
Автор FAQ
25.08.2011, 21:10 #17
Цитата Сообщение от AvengerAlive Посмотреть сообщение
mas=(int*)malloc((n+m+1)*sizeof(int));
- это не так делается, каждый раз память с нуля выделять
Алгоритм такой выделям память изначально malloc-ом, а затем изменяем её при помощи realloc, обрати внимание на вот эту строку моего топика
C++
1
bin = (char *)realloc(bin,(1 + (i = i + 1))*sizeof(char));
http://www.cyberforum.ru/cpp-beginners/thread345129.html#post1938658

Как пример конструкции malloc - realloc привожу проектик
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
#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
 
//Ввод до того как не введём символ окончания ввода, \n - нажмём Enter
char * get_text(char * s, char ch_end, int &sLen);
 
int main()
{
    int sLen = 0;
    char * str = (char *)malloc(sizeof(char));
    do
    {
        printf("\tEnter text\r\n");
        str = get_text(str, '\n', sLen);
        printf("\tYour input :\r\n%s\r\n",str);
        printf("[Y/N] Y - new input\r\n");
    }
    while(toupper(getch()) == 'Y');
    return 0;
}
 
char * get_text(char * s, char ch_end, int &sLen)
{
    sLen = 0;
    if(s)
    {
        while((s[sLen] = getchar()) != ch_end)
            s = (char *)realloc((void *)s,(1 + (sLen = sLen + 1))*sizeof(char));
        s[sLen] = '\0';//Избавляемся от мусора, вконце строки
    }
    return s;
}
0
Миниатюры
Молниеносное нахождение подстрок  
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:12  [ТС] #18
Сыроежка, Я говорю медленно работает моя прога с таким алгоритмом, а ты мне про find, который наивный. Существует сложность алгоримов, чем она меньше тем быстрее прога работает. Поэтому find не получается, с ним уже 5 тестов TL.


diagon, Задачка почти та, только надо количество вывести, а не каждый символ. Да и тестов там больше, и большие они.
0
Сыроежка
Заблокирован
25.08.2011, 21:13 #19
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Сыроежка, Я говорю медленно работает моя прога с таким алгоритмом, а ты мне про find, который наивный. Существует сложность алгоримов, чем она меньше тем быстрее прога работает. Поэтому find не получается, с ним уже 5 тестов TL.
До вас с первого раза не доходит? Ваша программа некорректная! Сколько еще раз повторять?!

Я вам уже сказал, что вам не о сложности надо рассуждать, а научиться писать элементарные конструкции на С++.
2
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
25.08.2011, 21:18  [ТС] #20
Сыроежка, чего там некорректного? Прошло 12 тестов из 15, да и ещё по причине TL, а так без TL прошло бы быстрее.
0
25.08.2011, 21:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.08.2011, 21:18
Привет! Вот еще темы с решениями:

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

Удаление всех подстрок из строки
Здравствуйте. После выполнения моей программы у меня выдает вот такую ошибку ...

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

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


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

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

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